#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 20;
vector<int> adj[maxN][2];
vector<pair<int, int>> ch[maxN][2];
pair<int, int> par[maxN][2];
int depth[maxN][2];
int cnt[maxN];
int root[2];
int Tin[maxN];
int Tout[maxN];
vector<vector<pair<int, pair<int, int>>>> queries[maxN];
vector<int> res;
int T;
int get_root(int u, int type) {
if (!par[u][type].second) {
return u;
}
else {
return get_root(par[u][type].second, type);
}
}
void join(int u, int v, int w, int type) {
int ru = get_root(u, type);
int rv = get_root(v, type);
if (ru == rv) {
return;
}
if (depth[ru][type] > depth[rv][type]) {
swap(ru, rv);
}
ch[rv][type].emplace_back(w, ru);
par[ru][type] = make_pair(w, rv);
if (depth[ru][type] == depth[rv][type]) {
depth[rv][type]++;
}
}
void dfs1(int u) {
Tin[u] = ++T;
for (auto e: ch[u][1]) {
dfs1(e.second);
}
Tout[u] = T;
}
void update(int u, int add) {
cnt[u] += add;
}
int get(int lt, int rt) {
int res = 0;
for (int i = lt; i <= rt; i++) {
res += cnt[i];
}
return res;
}
void dfs2(int u, int add) {
update(u, add);
for (auto e: ch[u][0]) {
dfs2(e.second, add);
}
}
void solve(int u) {
for (int iter = 0; iter < 2; iter++) {
int add = (iter ? -1 : 1);
for (int i = 0; i <= (int)ch[u][0].size(); i++) {
if (i == 0) {
update(u, add);
}
else {
dfs2(ch[u][0][i - 1].second, add);
}
if (!iter) {
for (auto q: queries[u][i]) {
int id = q.first;
int lt = q.second.first;
int rt = q.second.second;
res[id] = get(lt, rt) > 0;
}
}
}
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int M = X.size();
int Q = S.size();
for (int i = 0; i < M; i++) {
X[i]++;
Y[i]++;
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
adj[X[i]][0].push_back(Y[i]);
adj[Y[i]][1].push_back(X[i]);
}
for (int type = 0; type < 2; type++) {
for (int u = (type ? 1 : N); (type ? u <= N : u >= 1); u += (type ? 1 : -1)) {
for (auto v: adj[u][type]) {
join(u, v, u, type);
}
}
root[type] = get_root(1, type);
}
dfs1(root[1]);
for (int u = 1; u <= N; u++) {
queries[u].resize(ch[u][0].size() + 1);
}
res.resize(Q);
for (int id = 0; id < Q; id++) {
L[id]++;
R[id]++;
int u = S[id] + 1;
int v = E[id] + 1;
while (u != root[0] && par[u][0].first >= L[id]) {
u = par[u][0].second;
}
int pref_u = upper_bound(ch[u][0].begin(), ch[u][0].end(), make_pair(L[id], 0), greater<pair<int, int>>()) - ch[u][0].begin();
while (v != root[1] && par[v][1].first <= R[id]) {
v = par[v][1].second;
}
int pref_v = upper_bound(ch[v][1].begin(), ch[v][1].end(), make_pair(R[id], N + 1)) - ch[v][1].begin();
for (int j = 1; j <= N; j++) {
cnt[j] = 0;
}
int lt = Tin[v];
int rt = (pref_v ? Tout[ch[v][1][pref_v - 1].second] : lt);
queries[u][pref_u].emplace_back(id, make_pair(lt, rt));
}
for (int u = 1; u <= N; u++) {
solve(u);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2709 ms |
71388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
