#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 200001;
int n, par[MX][2];
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];
}
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);
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];
while (par[s][0] >= l) s = par[s][0];
while (par[e][1] <= r) e = par[e][1];
for (int x = l; x <= r; x++) {
if (is_anc(s, x, 0) && is_anc(e, x, 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:70: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]
70 | while (ptr < ed.size() && min(ed[ptr].first, ed[ptr].second) == i) {
| ~~~~^~~~~~~~~~~
werewolf.cpp: In function 'void BuildLarge()':
werewolf.cpp:132: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]
132 | while (ptr < ed.size() && max(ed[ptr].first, ed[ptr].second) == i) {
| ~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4025 ms |
14400 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4025 ms |
14400 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4032 ms |
53968 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4025 ms |
14400 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
