#include "island.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define INF (1<<30)
#define INFL (1LL<<60)
#define EPS ((ld)(1e-9))
#define sz(x) ((int)(x).size())
#define setz(x) memset(x, 0, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define rep(i, e) for (int i = 0, _##i = (e); i < _##i; i++)
#define repp(i, s, e) for (int i = (s), _##i = (e); i < _##i; i++)
#define repr(i, s, e) for (int i = (s)-1, _##i = (e); i >= _##i; i--)
#define repi(i, x) for (auto &i : (x))
#define ARR(...) vector<int>({__VA_ARGS__})
#define ARS(...) vector<string>({__VA_ARGS__})
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef complex<double> base;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
template<typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) {
return os << '(' << pai.first << ' ' << pai.second << ')';
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
cout << '[';
for (auto p : v) cout << p << ",";
cout << "]";
return os;
}
template<typename T, typename V>
ostream &operator<<(ostream &os, const set<T, V> v) {
cout << "{";
for (auto p : v) cout << p << ",";
cout << "}";
return os;
}
template<typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
cout << "{";
for (auto p : v) cout << p << ",";
cout << "}";
return os;
}
#ifndef __SOULTCH
#define debug(...) 0
#define endl '\n'
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
while(*sdbg != ',') cout << *sdbg++;
cout << '=' << (h) << ',';
_dbg(sdbg+1, a...);
}
#endif
template<typename T> void get_max(T &a, T b) {a = max(a, b);}
template<typename T> void get_min(T &a, T b) {a = min(a, b);}
const int MAXN = 500000;
int K, N, M, X;
int root[MAXN];
int par[MAXN];
int dep[MAXN];
int _lca[MAXN][20];
int minv[MAXN];
int find(int p) {return root[p]==p?p:root[p]=find(root[p]);}
void connect(int a, int b, int v) {
a = find(a), b = find(b);
if (a != b) {
int num = X++;
root[a] = par[a] = num;
root[b] = par[b] = num;
minv[num] = v;
}
}
void Init(int KK, vector<int> F, vector<int> S, vector<int> E){
K = KK, N = F.size(), M = S.size(), X = K+N+1;
debug(X);
rep(i, MAXN) root[i] = i;
repr(i, M, 0) {
connect(S[i]+1, E[i]+1, i+1);
connect(N+F[S[i]]+1, E[i]+1, i+1);
connect(S[i]+1, N+F[E[i]]+1, i+1);
}
repr(i, X, 1) {
dep[i] = dep[par[i]]+1;
_lca[i][0] = par[i];
repp(j, 1, 20) _lca[i][j] = _lca[_lca[i][j-1]][j-1];
}
rep(i, X) debug(i, _lca[i][1], minv[i]);
}
int lca(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
int dif = dep[b]-dep[a];
rep(i, 20) if (dif&(1<<i)) b = _lca[b][i];
if (a == b) return a;
repr(i, 20, 0) if (_lca[a][i] != _lca[b][i]) a = _lca[a][i], b = _lca[b][i];
return _lca[a][0];
}
int Separate(int A, int B){
debug(lca(6, 7));
int a = A+N+1, b = B+N+1;
int p = lca(a, b);
return minv[p];
}
Compilation message
island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:102:10: warning: statement has no effect [-Wunused-value]
debug(X);
^
island.cpp:116:41: warning: statement has no effect [-Wunused-value]
rep(i, X) debug(i, _lca[i][1], minv[i]);
^
island.cpp: In function 'int Separate(int, int)':
island.cpp:133:18: warning: statement has no effect [-Wunused-value]
debug(lca(6, 7));
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
515 ms |
43488 KB |
Output is correct |
| 2 |
Correct |
485 ms |
43488 KB |
Output is correct |
| 3 |
Correct |
533 ms |
43488 KB |
Output is correct |
| 4 |
Correct |
568 ms |
43492 KB |
Output is correct |
| 5 |
Correct |
543 ms |
43492 KB |
Output is correct |
| 6 |
Correct |
513 ms |
43492 KB |
Output is correct |
| 7 |
Correct |
577 ms |
43488 KB |
Output is correct |
| 8 |
Correct |
484 ms |
43512 KB |
Output is correct |
| 9 |
Correct |
784 ms |
43488 KB |
Output is correct |
| 10 |
Correct |
529 ms |
43488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
