#include "island.h"
//#include "header.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
int isl[100010];
int p[100010];
int unf(int a) { return p[a] = (a == p[a]) ? a : unf(p[a]); }
class LCA { // 1-indexed
public:
vector < vector< pair<int, int> > > adj;
vector< vector<int> > anc, minv; // anc[i][j] : 2**j-th ancestor of i
vector<int> depth;
int n, mxdepth;
LCA(int n) :n(n), adj(n + 1), depth(n + 1), anc(n + 1), minv(n + 1) {
mxdepth = 20;
for (int i = 0; i <= n; i++) anc[i].resize(mxdepth);
for (int i = 0; i <= n; i++) minv[i].resize(mxdepth);
}
void construct(int cur, int p, int v) {
depth[cur] = depth[p] + 1;
anc[cur][0] = p;
minv[cur][0] = v;
for (int i = 1; i < mxdepth; i++)
{
anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
minv[cur][i] = min(minv[cur][i - 1], minv[anc[cur][i - 1]][i - 1]);
}
for (auto n : adj[cur]) {
if (n.X != p) construct(n.X, cur, n.Y);
}
}
void construct(int root) { // set anc table
construct(root, 0, 0);
}
int lca(int a, int b) { // returns lca of a,b
if (depth[a] > depth[b]) swap(a, b);
int ret = 0x7f7f7f7f;
for (int i = mxdepth - 1; i >= 0; i--) {
if (depth[a] <= depth[anc[b][i]])
{
ret = min(ret, minv[b][i]);
b = anc[b][i];
}
}
if (a != b) {
for (int j = mxdepth - 1; j >= 0; j--) {
if (anc[a][j] != 0 and anc[a][j] != anc[b][j]) {
ret = min(ret, min(minv[a][j], minv[b][j]));
a = anc[a][j];
b = anc[b][j];
}
}
ret = anc[a][0];
}
return ret;
}
void pushadj(int a, int b, int v) {
adj[a].pb({ b, v });
adj[b].pb({ a, v });
}
};
LCA* lca;
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E) {
int N = F.size(), M = S.size();
lca = new LCA(N);
for (int i = 0; i < M; i++)
S[i]++, E[i]++;
for (int i = 0; i < N; i++)
isl[F[i]] = i + 1;
for (int i = 1; i <= N; i++) p[i] = i;
for (int i = M - 1; i >= 0; i--)
{
int a = S[i], b = E[i];
a = unf(a); b = unf(b);
if (a == b) continue;
lca->pushadj(S[i], E[i], i);
p[b] = a;
}
lca->construct(N / 2 + 1);
}
int Separate(int A, int B) {
A = isl[A]; B = isl[B];
return lca->lca(A, B) + 1;
}
/*
5 6 3 3
0 1 2 0 1
0 1
2 3
2 4
4 3
1 2
0 4
*/
Compilation message
island.cpp: In constructor 'LCA::LCA(int)':
island.cpp:21:6: warning: 'LCA::n' will be initialized after [-Wreorder]
int n, mxdepth;
^
island.cpp:18:38: warning: 'std::vector<std::vector<std::pair<int, int> > > LCA::adj' [-Wreorder]
vector < vector< pair<int, int> > > adj;
^~~
island.cpp:22:2: warning: when initialized here [-Wreorder]
LCA(int n) :n(n), adj(n + 1), depth(n + 1), anc(n + 1), minv(n + 1) {
^~~
island.cpp:20:14: warning: 'LCA::depth' will be initialized after [-Wreorder]
vector<int> depth;
^~~~~
island.cpp:19:24: warning: 'std::vector<std::vector<int> > LCA::anc' [-Wreorder]
vector< vector<int> > anc, minv; // anc[i][j] : 2**j-th ancestor of i
^~~
island.cpp:22:2: warning: when initialized here [-Wreorder]
LCA(int n) :n(n), adj(n + 1), depth(n + 1), anc(n + 1), minv(n + 1) {
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
330 ms |
36496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
