#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define pi pair<int, int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
vector<int> adj[200000];
vector<int> adj2[200000];
int smallIdx[200000];
int smallStart[200000];
int smallEnd[200000];
int largeIdx[200000];
int largeStart[200000];
int largeEnd[200000];
int pa[200000];
int parSmall[200000][20];
int parLarge[200000][20];
int sz[200000];
int smallest[200000];
int largest[200000];
int ctr = 0;
void dfs(int u, int *idx, int *start, int *end) {
start[u] = ctr;
for (int v : adj2[u]) {
dfs(v, idx, start, end);
}
end[u] = ctr;
idx[u] = ctr++;
}
int get(int x) { return x == pa[x] ? x : pa[x] = get(pa[x]); }
void unite(int a, int b) {
a = get(a), b = get(b);
if (a == b) return;
if (sz[a] > sz[b]) swap(a, b);
pa[a] = b;
sz[b] += sz[a];
if (smallest[b] > smallest[a]) {
// put b as child of a
adj2[smallest[a]].pb(smallest[b]);
parSmall[smallest[b]][0] = smallest[a];
} else {
adj2[smallest[b]].pb(smallest[a]);
parSmall[smallest[a]][0] = smallest[b];
}
smallest[b] = min(smallest[b], smallest[a]);
}
void unite2(int a, int b) {
a = get(a), b = get(b);
if (a == b) return;
if (sz[a] > sz[b]) swap(a, b);
pa[a] = b;
sz[b] += sz[a];
if (largest[b] < largest[a]) {
// put b as child of a
adj2[largest[a]].pb(largest[b]);
parLarge[largest[b]][0] = largest[a];
} else {
adj2[largest[b]].pb(largest[a]);
parLarge[largest[a]][0] = largest[b];
}
largest[b] = max(largest[b], largest[a]);
}
vector<int> check_validity(int n, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
for (int i = 0; i < (int)X.size(); i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int i = 0; i < n; i++) {
pa[i] = i;
sz[i] = 1;
smallest[i] = i;
}
for (int i = n-1; ~i; i--) {
for (int v : adj[i]) {
if (v > i) {
unite(v, i);
}
}
}
ctr = 0;
dfs(0, smallIdx, smallStart, smallEnd);
parSmall[0][0] = 0;
for (int i = 0; i < n; i++) {
pa[i] = i;
sz[i] = 1;
largest[i] = i;
adj2[i].clear();
}
for (int i = 0; i < n; i++) {
for (int v : adj[i]) {
if (v < i) {
unite2(v, i);
}
}
}
ctr = 0;
dfs(n-1, largeIdx, largeStart, largeEnd);
parLarge[n-1][n-1] = n-1;
vector<int> A(S.size(), 0);
for (int i = 0; i < (int)S.size(); i++) {
int u = S[i];
while (parSmall[u][0] >= L[i]) {
u = parSmall[u][0];
if (u == parSmall[u][0]) break;
}
int smallLeft = smallStart[u], smallRight = smallEnd[u];
u = E[i];
while (parLarge[u][0] <= R[i]) {
u = parLarge[u][0];
if (u == parLarge[u][0]) break;
}
int largeLeft = largeStart[u], largeRight = largeEnd[u];
//cout << u << " " << smallLeft << " " << smallRight << " " << largeLeft << " " << largeRight << endl;
for (int j = 0; j < n; j++) {
if (largeLeft <= largeIdx[j] && largeIdx[j] <= largeRight) {
if (smallLeft <= smallIdx[j] && smallIdx[j] <= smallRight) {
A[i] = 1;
}
}
}
}
return A;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4058 ms |
9836 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4058 ms |
9836 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4091 ms |
80052 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4058 ms |
9836 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |