n*logn*logn不能过1e5吗
查看原帖
n*logn*logn不能过1e5吗
327139
纯白楼主2024/2/29 22:57
#include <bits/stdc++.h>
const int maxn = 100000 + 10;
using namespace std;
int p[maxn], fa[maxn], to[maxn];
vector<set<int>> v;
int n, m;
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
    int fax = find(x), fay = find(y);
    if (fax == fay)
        return;
    if (v[fax].size() < v[fay].size())
        swap(fax, fay);
    fa[fay] = fax;
    for (auto i : v[fay])
    {
        if (!v[fax].count(i))
            v[fax].insert(i);
    }
    v[fay].clear();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        to[p[i]] = i;
    }
    v.resize(n + 1);
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        v[i].insert(p[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }
    int t;
    cin >> t;
    while (t--)
    {
        char c;
        cin >> c;
        int x, y;
        cin >> x >> y;
        if (c == 'B')
        {
            merge(x, y);
        }
        else
        {
            int fax = find(x);
            if (y > v[fax].size())
            {
                cout << -1 << "\n";
                continue;
            }
            auto it = v[fax].begin();
            advance(it, y - 1);
            cout << to[*it] << "\n";
        }
    }
}```
这份代码的时间复杂度应该没有算错吧,开了o2,tle#10。   
请问问题在哪呢
2024/2/29 22:57
加载中...