#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 200001;
const int LG = 25;
int n, par[MX][2], fs[MX][LG], fe[MX][LG];
vector<int> adj[MX], e[MX][2];
vector<pair<int, int>> ed;
struct DSU {
int fa[MX];
void init() { iota(fa, fa + MX, 0); }
DSU() { init(); }
int root(int x) { return fa[x] == x ? x : fa[x] = root(fa[x]); }
void unite(int x, int y) { fa[root(x)] = root(y); }
};
void BuildSmall() {
// 0 is root
vector<int> fa(n), sz(n), mn(n);
for (int i = 0; i < n; i++) {
fa[i] = i;
sz[i] = 1;
mn[i] = i;
}
struct op {
int root_a;
int root_b;
int sz_a;
int sz_b;
int mn_a;
int mn_b;
};
stack<op> stk;
function<int(int)> root = [&](int x) {
return fa[x] == x ? x : root(fa[x]);
};
function<void(int, int)> unite = [&](int x, int y) {
x = root(x);
y = root(y);
if (sz[x] < sz[y]) swap(x, y);
stk.push({x, y, sz[x], sz[y], mn[x], mn[y]});
if (x == y) return;
fa[y] = x;
sz[x] += sz[y];
mn[x] = min(mn[x], mn[y]);
};
function<void()> roll = [&]() {
op lst = stk.top();
stk.pop();
fa[lst.root_a] = lst.root_a;
fa[lst.root_b] = lst.root_b;
sz[lst.root_a] = lst.sz_a;
sz[lst.root_b] = lst.sz_b;
mn[lst.root_a] = lst.mn_a;
mn[lst.root_b] = lst.mn_b;
};
sort(ed.begin(), ed.end(), [&](pair<int, int> x, pair<int, int> y) {
return min(x.first, x.second) < min(y.first, y.second);
});
for (int i = ed.size() - 1; i >= 0; i--) {
unite(ed[i].first, ed[i].second);
}
for (int i = 1; i < n; i++)
par[i][0] = -1;
int ptr = 0;
for (int i = 0; i < n; i++) {
while (ptr < ed.size() && min(ed[ptr].first, ed[ptr].second) == i) {
roll();
ptr++;
}
for (int j : adj[i]) {
int oth = mn[root(j)];
if (par[oth][0] == -1) par[oth][0] = i;
}
}
}
void BuildLarge() {
// n-1 is root
vector<int> fa(n), sz(n), mx(n);
for (int i = 0; i < n; i++) {
fa[i] = i;
sz[i] = 1;
mx[i] = i;
}
struct op {
int root_a;
int root_b;
int sz_a;
int sz_b;
int mx_a;
int mx_b;
};
stack<op> stk;
function<int(int)> root = [&](int x) {
return fa[x] == x ? x : root(fa[x]);
};
function<void(int, int)> unite = [&](int x, int y) {
x = root(x);
y = root(y);
if (sz[x] < sz[y]) swap(x, y);
stk.push({x, y, sz[x], sz[y], mx[x], mx[y]});
if (x == y) return;
fa[y] = x;
sz[x] += sz[y];
mx[x] = max(mx[x], mx[y]);
};
function<void()> roll = [&]() {
op lst = stk.top();
stk.pop();
fa[lst.root_a] = lst.root_a;
fa[lst.root_b] = lst.root_b;
sz[lst.root_a] = lst.sz_a;
sz[lst.root_b] = lst.sz_b;
mx[lst.root_a] = lst.mx_a;
mx[lst.root_b] = lst.mx_b;
};
sort(ed.begin(), ed.end(), [&](pair<int, int> x, pair<int, int> y) {
return max(x.first, x.second) > max(y.first, y.second);
});
for (int i = ed.size(); i >= 0; i--) {
unite(ed[i].first, ed[i].second);
}
for (int i = 0; i < n - 1; i++)
par[i][1] = -1;
par[n - 1][1] = n - 1;
int ptr = 0;
for (int i = n - 1; i >= 0; i--) {
while (ptr < ed.size() && max(ed[ptr].first, ed[ptr].second) == i) {
roll();
ptr++;
}
for (int j : adj[i]) {
int oth = mx[root(j)];
if (par[oth][1] == -1) par[oth][1] = i;
}
}
}
int tin[MX][2], tout[MX][2], tajm[2];
void dfs(int u, int pa, int t) {
tin[u][t] = ++tajm[t];
for (int v : e[u][t])
if (v != pa)
dfs(v, u, t);
tout[u][t] = tajm[t];
}
bool is_anc(int x, int y, int t) {
return tin[x][t] <= tin[y][t] && tout[y][t] <= tout[x][t];
}
const int M = 20 * MX;
int root[MX], ls[M], rs[M], st[M], tsz;
void update(int& c, int p, int ss, int se, int qi) {
c = ++tsz; ls[c] = ls[p]; rs[c] = rs[p]; st[c] = st[p] + 1;
if (ss == se) return;
int mid = ss + se >> 1;
if (qi <= mid) update(ls[c], ls[p], ss, mid, qi);
else update(rs[c], rs[p], mid + 1, se, qi);
}
int query(int c, int p, int ss, int se, int qs, int qe) {
if (ss > qe || se < qs) return 0;
if (qs <= ss && se <= qe) return st[c] - st[p];
int mid = ss + se >> 1;
return query(ls[c], ls[p], ss, mid, qe, se)
+ query(rs[c], rs[p], mid + 1, se, qs, qe);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
n = N;
int M = X.size();
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
ed.emplace_back(X[i], Y[i]);
}
BuildSmall();
BuildLarge();
/*puts("Small parent");
for (int i = 0; i < n; i++) cout << par[i][0] << " ";
puts("Large parent");
for (int i = 0; i < n; i++) cout << par[i][1] << " ";*/
for (int i = 1; i < n; i++) {
e[par[i][0]][0].push_back(i);
}
for (int i = 0; i < n; i++) {
e[par[i][1]][1].push_back(i);
}
dfs(0, 0, 0);
dfs(n - 1, n - 1, 1);
for (int i = 0; i < n; i++)
fs[i][0] = par[i][0];
for (int i = 0; i < n; i++)
fe[i][0] = par[i][1];
for (int j = 1; j < LG; j++) {
for (int i = 0; i < n; i++) {
fs[i][j] = fs[fs[i][j - 1]][j - 1];
fe[i][j] = fe[fe[i][j - 1]][j - 1];
}
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return tin[i][0] < tin[j][0];
});
for (int i = 1; i <= n; i++) {
update(root[i], root[i - 1], 1, n, tin[ord[i - 1]][1]);
}
int Q = S.size();
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
int l = L[i];
int r = R[i];
int s = S[i];
int e = E[i];
for (int j = LG - 1; j >= 0; j--) {
if (fs[s][j] >= l) s = fs[s][j];
if (fe[e][j] <= r) e = fe[e][j];
}
if (query(root[tout[s][0]], root[tin[s][0] - 1], 1, n, tin[e][1], tout[e][1])) ans[i] = 1;
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
Compilation message
werewolf.cpp: In function 'void BuildSmall()':
werewolf.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | while (ptr < ed.size() && min(ed[ptr].first, ed[ptr].second) == i) {
| ~~~~^~~~~~~~~~~
werewolf.cpp: In function 'void BuildLarge()':
werewolf.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | while (ptr < ed.size() && max(ed[ptr].first, ed[ptr].second) == i) {
| ~~~~^~~~~~~~~~~
werewolf.cpp: In function 'void update(int&, int, int, int, int)':
werewolf.cpp:165:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
165 | int mid = ss + se >> 1;
| ~~~^~~~
werewolf.cpp: In function 'int query(int, int, int, int, int, int)':
werewolf.cpp:173:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
173 | int mid = ss + se >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
693 ms |
130148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
