#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define vi vector<int>
#define pii pair<int, int>
struct KRT{
int n, id;
vector<int> p, eu, in, ou, s, mx;
vector<vector<int>> gr;
KRT(int N){
this->n = N;
this->id = 1;
p.assign(2*N + 5, 0);
s.assign(2*N + 5, 0);
mx.assign(2*N + 5, 0);
eu.assign(4*N + 5, 0);
in.assign(2*N + 5, 0);
ou.assign(2*N + 5, 0);
gr.assign(2*N + 5, vector<int>());
for(int i=1; i<=2*n; ++i){
mx[i] = p[i] = i;
s[i] = 1;
}
}
int find(int u){
return (u == p[u] ? u : p[u] = find(p[u]));
}
int get(int u){
return mx[find(u)];
}
void add_edge(int u, int v){
u = find(u), v = find(v);
if(u == v){
return;
}
++n;
gr[n].push_back(mx[u]);
gr[n].push_back(mx[v]);
if(s[u] < s[v]){
swap(u, v);
}
s[u] += s[v];
p[v] = u;
mx[u] = n;
}
void dfs(int u){
in[u] = id;
int f = 0;
for(int v : gr[u]){
dfs(v);
f = 1;
}
if(!f){
eu[++id] = u;
}
ou[u] = id - 1;
}
};
struct BIT{
int n;
vector<int> f;
BIT(int N){
this->n = N + 5;
f.assign(N + 5, 0);
}
void update(int i, int val){
while(i < n){
f[i] += val;
i += (i & -i);
}
}
int get(int i){
int ans = 0;
while(i > 0){
ans += f[i];
i -= (i & -i);
}
return ans;
}
int get(int l, int r){
return get(r) - get(l-1);
}
};
const int MX = 1e6 + 5;
vector<vector<int>> Q[MX];
vector<pii> pf[MX], sf[MX];
vector<pii> wolf[MX], human[MX];
int pf_id[MX], sf_id[MX];
int L[MX], R[MX];
int l1[MX], r1[MX], l2[MX], r2[MX];
int pos[MX], f[MX];
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R){
int n = N, m = X.size(), q = S.size();
for(int i=0; i<m; ++i){
int u = ++X[i], v = ++Y[i];
pf[max(u, v)].push_back({u, v});
sf[min(u, v)].push_back({u, v});
}
for(int i=0; i<q; ++i){
int s = ++S[i], e = ++E[i], l = ++L[i], r = ++R[i];
human[l].push_back({s, i});
wolf[r].push_back({e, i});
}
KRT up(n), dn(n);
for(int i=1; i<=n; ++i){
for(pii p : pf[i]){
int u, v;
tie(u, v) = p;
up.add_edge(u, v);
}
for(pii p : wolf[i]){
int u, idx;
tie(u, idx) = p;
pf_id[idx] = up.get(u);
}
}
for(int i=n; i>=1; --i){
for(pii p : sf[i]){
int u, v;
tie(u, v) = p;
dn.add_edge(u, v);
}
for(pii p : human[i]){
int u, idx;
tie(u, idx) = p;
sf_id[idx] = dn.get(u);
}
}
up.dfs(up.n);
dn.dfs(dn.n);
for(int i=1; i<=up.id; ++i){
pos[up.eu[i]] = i;
}
int idx = 0;
for(int i=0; i<q; ++i){
int l = up.in[pf_id[i]], r = up.ou[pf_id[i]], u = dn.in[sf_id[i]], v = dn.ou[sf_id[i]];
Q[v].push_back({l, r, idx});
L[i] = idx++;
Q[u - 1].push_back({l, r, idx});
R[i] = idx++;
}
BIT bit(up.id);
for(int i=1; i<=up.id; ++i){
int x = pos[up.eu[i]];
bit.update(x, 1);
for(vector<int> v : Q[i]){
int l = v[0], r = v[1], idx = v[2];
f[idx] = bit.get(l, r);
}
}
vector<int> ans;
for(int i=0; i<q; ++i){
int val = (f[R[i]] - f[L[i]] != 0);
ans.push_back(val);
}
return ans;
}
// int32_t main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// freopen("main.inp","r",stdin);
// freopen("main.out","w",stdout);
// // check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
// // {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
// vector<int> ans = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
// {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
// for(int x : ans){
// cout<<x<<endl;
// }
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
126036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
126036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
563 ms |
236232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
126036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
