#include <bits/stdc++.h>
#include "island.h"
using namespace std;
struct DSU
{
vector<int> dsu;
DSU(int n) : dsu(n+1, -1) { }
int get(int x) {
if(dsu[x] < 0) {
return x;
}
return get(dsu[x]);
}
bool merge(int x, int y) { // merge x to y
x = get(x), y = get(y);
if(x == y) {
return false;
}
dsu[y] += dsu[x];
dsu[x] = y;
return true;
}
};
void solve(int N, int L) {
vector<int> by_one {1}, order(N+1, -1);
order[1] = 0;
for(int i = 1; i < N; ++i) {
by_one.push_back(query(1, i));
order[by_one.back()] = i;
}
vector<int> par(N+1, -1);
DSU dsu(N);
for(int i = 2; i <= N; ++i) {
int cnt = 1;
while(par[i] == -1) {
const int x = query(i, cnt);
if(order[x] < order[i]) {
assert(dsu.merge(i, x));
par[i] = x;
}
else {
assert(dsu.merge(x, i));
par[x] = i;
}
cnt++;
}
}
for(int i = 2; i <= N; ++i) {
assert(par[i] != -1);
answer(i, par[i]);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |