#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
ll fen[N];
void modif(int u, int val) {
for(int i = u + 1; i < N; i += i & -i) fen[i] += val;
}
ll query(int l, int r) {
ll ans = 0;
for(int i = r + 1; i > 0; i -= i & -i) ans += fen[i];
for(int i = l; i > 0; i -= i & -i) ans -= fen[i];
return ans;
}
struct dsu {
vector<int> p;
dsu(int n) {
p.resize(n); iota(p.begin(), p.end(), 0);
}
int get(int a) {
return (a == p[a] ? a : get(p[a]));
}
void uni(int a, int b) {
a = get(a), b = get(b);
if(a == b) return;
p[a] = b;
}
};
void dfs(int u, vector<int>& p, vector<int>& s, vector<vector<int>>& adj, int& tt) {
p[u] = tt++;
s[u] = 1;
for(int v: adj[u]) {
dfs(v, p, s, adj, tt);
s[u] += s[v];
}
}
std::vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, std::vector<int> E,
vector<int> L, std::vector<int> R) {
for(int i = 0; i < N; ++i) fen[i] = 0;
int Q = S.size(), paiu = 0, moment = 0;
vector<int> ans(Q, 0);
vector<vector<int>> g1(n), g2(n), g(n);
for(int i = 0; i < (int)X.size(); ++i) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
dsu d1(n), d2(n);
for(int i = n - 1; i >= 0; --i) {
set<int> st;
for(int j: g[i]) {
if(i < j && d1.get(i) != d1.get(j)) st.insert(d1.get(j));
}
for(auto x: st) {
g1[i].push_back(d1.get(x));
d1.uni(x, i);
}
}
for(int i = 0; i < n; ++i) {
set<int> st;
for(int j: g[i]) {
if(i > j && d2.get(i) != d2.get(j)) st.insert(d2.get(j));
}
for(auto x: st) {
g2[i].push_back(d2.get(x));
d2.uni(x, i);
}
}
vector<int> p1(n, -1), s1(n), p2(n, -1), s2(n);
dfs(0, p1, s1, g1, paiu);
dfs(n - 1, p2, s2, g2, moment);
for(int i = 0; i < n; ++i) {
assert(p1[i] != -1 && p2[i] != -1);
}
vector<int> events[n], nodes(n);
for(int i = 0; i < n; ++i) nodes[p1[i]] = p2[i];
for(int i = 0; i < Q; ++i) {
int node = L[i];
events[p1[node]].push_back(-1);
events[p1[node] + s1[node] - 1].push_back(i);
}
for(int i = 0; i < n; ++i) {
sort(events[i].begin(), events[i].end());
for(int j: events[i]) {
if(j < 0) {
modif(nodes[i], 1);
} else {
int node = R[j];
int nodeL = L[j];
assert(query(p2[node], p2[node] + s2[node] - 1) >= 0);
if(query(p2[node], p2[node] + s2[node] - 1) > 0) {
if(p1[nodeL] <= p1[S[j]] && p1[S[j]] <= i && p2[node] <= p2[E[j]] && p2[E[j]] <= p2[node] + s2[node] - 1) {
ans[j] = 1;
}
}
}
}
for(int j: events[i]) {
if(j >= 0) {
modif(nodes[i], -1);
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
3668 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
3668 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
408 ms |
112776 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
3668 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
