/*
We build a prefix and suffix tree with dsu, by incrementing them by 1 vertex at each step. Now queries become:
Do two subtrees have a common vertex (the first subtree is from the prefix tree and the second subtree is from the suffix tree).
This can be done with DFS order + dsu on tree by keeping a set for each vertex. The complexity will be O(N log^2 N + Q log N).
*/
#include <bits/stdc++.h>
#include "werewolf.h"
//#include "grader.cpp"
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
using namespace std;
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int tp[MAXN], sz[MAXN], par[MAXN];
void init(int n)
{
for(int i = 0; i <= n; i++)
par[i] = i, sz[i] = 1, tp[i] = i;
}
int root(int x) { return x == par[x] ? x : (par[x] = root(par[x])); }
bool connected(int u, int v)
{
return root(u) == root(v);
}
void unite(int u, int v)
{
u = root(u), v = root(v);
if(u == v) return;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v;
sz[v] += sz[u];
}
struct Tree
{
vector<int> adj[MAXN];
int st[MAXN], en[MAXN], dfs_time;
void add_edge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void pre_dfs(int u, int pr)
{
st[u] = ++dfs_time;
for(int v: adj[u])
if(v != pr)
pre_dfs(v, u);
en[u] = dfs_time;
}
void order(int root)
{
dfs_time = 0;
pre_dfs(root, root);
}
} t1, t2;
vector<int> adj[MAXN];
vector<int> pref[MAXN], suff[MAXN];
vector<int> ans;
int vert1[MAXN], vert2[MAXN];
set<int> st[MAXN];
vector<int> que[MAXN];
void solve(int u, int pr = -1)
{
st[u].insert(t1.st[u]);
for(int v: t2.adj[u])
if(v != pr)
{
solve(v, u);
if(st[u].size() < st[v].size()) swap(st[u], st[v]);
for(int x: st[v])
st[u].insert(x);
st[v].clear();
}
for(int i: que[u])
{
int L = t1.st[vert1[i]], R = t1.en[vert1[i]];
auto it = st[u].lower_bound(L);
if(it != st[u].end() && *it <= R)
ans[i] = 1;
}
}
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R)
{
int q = S.size(), m = X.size();
ans.assign(q, 0);
for(int i = 0; i < m; i++)
{
int u = X[i], v = Y[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 0; i < q; i++)
{
suff[L[i]].push_back(i);
pref[R[i]].push_back(i);
}
init(n);
for(int i = 0; i < n; i++)
{
for(int v: adj[i])
if(i > v)
if(!connected(i, v))
{
t1.add_edge(tp[root(i)], tp[root(v)]);
unite(i, v);
tp[root(i)] = i;
}
for(int it: pref[i])
vert1[it] = tp[root(E[it])];
}
int r1 = tp[root(0)];
t1.order(r1);
init(n);
for(int i = n - 1; i >= 0; i--)
{
for(int v: adj[i])
if(i < v)
if(!connected(i, v))
{
t2.add_edge(tp[root(i)], tp[root(v)]);
unite(i, v);
tp[root(i)] = i;
}
for(int it: suff[i])
vert2[it] = tp[root(S[it])];
}
int r2 = tp[root(0)];
t2.order(r2);
for(int i = 0; i < q; i++)
que[vert2[i]].push_back(i);
solve(r2);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
197496 KB |
Output is correct |
2 |
Correct |
189 ms |
197496 KB |
Output is correct |
3 |
Correct |
190 ms |
197496 KB |
Output is correct |
4 |
Correct |
187 ms |
197652 KB |
Output is correct |
5 |
Correct |
187 ms |
197704 KB |
Output is correct |
6 |
Correct |
189 ms |
197704 KB |
Output is correct |
7 |
Correct |
183 ms |
197704 KB |
Output is correct |
8 |
Correct |
190 ms |
197804 KB |
Output is correct |
9 |
Correct |
182 ms |
197804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
197496 KB |
Output is correct |
2 |
Correct |
189 ms |
197496 KB |
Output is correct |
3 |
Correct |
190 ms |
197496 KB |
Output is correct |
4 |
Correct |
187 ms |
197652 KB |
Output is correct |
5 |
Correct |
187 ms |
197704 KB |
Output is correct |
6 |
Correct |
189 ms |
197704 KB |
Output is correct |
7 |
Correct |
183 ms |
197704 KB |
Output is correct |
8 |
Correct |
190 ms |
197804 KB |
Output is correct |
9 |
Correct |
182 ms |
197804 KB |
Output is correct |
10 |
Correct |
192 ms |
198920 KB |
Output is correct |
11 |
Correct |
193 ms |
198920 KB |
Output is correct |
12 |
Correct |
206 ms |
199004 KB |
Output is correct |
13 |
Correct |
193 ms |
199124 KB |
Output is correct |
14 |
Correct |
195 ms |
199352 KB |
Output is correct |
15 |
Correct |
197 ms |
199464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1314 ms |
265088 KB |
Output is correct |
2 |
Correct |
1012 ms |
271860 KB |
Output is correct |
3 |
Correct |
1020 ms |
278448 KB |
Output is correct |
4 |
Correct |
1089 ms |
286548 KB |
Output is correct |
5 |
Correct |
1177 ms |
295756 KB |
Output is correct |
6 |
Correct |
1245 ms |
305844 KB |
Output is correct |
7 |
Correct |
1165 ms |
312440 KB |
Output is correct |
8 |
Correct |
992 ms |
322420 KB |
Output is correct |
9 |
Correct |
984 ms |
326080 KB |
Output is correct |
10 |
Correct |
1008 ms |
334100 KB |
Output is correct |
11 |
Correct |
1084 ms |
334344 KB |
Output is correct |
12 |
Correct |
1167 ms |
344456 KB |
Output is correct |
13 |
Correct |
1037 ms |
360052 KB |
Output is correct |
14 |
Correct |
1038 ms |
368524 KB |
Output is correct |
15 |
Correct |
1084 ms |
376920 KB |
Output is correct |
16 |
Correct |
1217 ms |
385416 KB |
Output is correct |
17 |
Correct |
1207 ms |
385416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
197496 KB |
Output is correct |
2 |
Correct |
189 ms |
197496 KB |
Output is correct |
3 |
Correct |
190 ms |
197496 KB |
Output is correct |
4 |
Correct |
187 ms |
197652 KB |
Output is correct |
5 |
Correct |
187 ms |
197704 KB |
Output is correct |
6 |
Correct |
189 ms |
197704 KB |
Output is correct |
7 |
Correct |
183 ms |
197704 KB |
Output is correct |
8 |
Correct |
190 ms |
197804 KB |
Output is correct |
9 |
Correct |
182 ms |
197804 KB |
Output is correct |
10 |
Correct |
192 ms |
198920 KB |
Output is correct |
11 |
Correct |
193 ms |
198920 KB |
Output is correct |
12 |
Correct |
206 ms |
199004 KB |
Output is correct |
13 |
Correct |
193 ms |
199124 KB |
Output is correct |
14 |
Correct |
195 ms |
199352 KB |
Output is correct |
15 |
Correct |
197 ms |
199464 KB |
Output is correct |
16 |
Correct |
1314 ms |
265088 KB |
Output is correct |
17 |
Correct |
1012 ms |
271860 KB |
Output is correct |
18 |
Correct |
1020 ms |
278448 KB |
Output is correct |
19 |
Correct |
1089 ms |
286548 KB |
Output is correct |
20 |
Correct |
1177 ms |
295756 KB |
Output is correct |
21 |
Correct |
1245 ms |
305844 KB |
Output is correct |
22 |
Correct |
1165 ms |
312440 KB |
Output is correct |
23 |
Correct |
992 ms |
322420 KB |
Output is correct |
24 |
Correct |
984 ms |
326080 KB |
Output is correct |
25 |
Correct |
1008 ms |
334100 KB |
Output is correct |
26 |
Correct |
1084 ms |
334344 KB |
Output is correct |
27 |
Correct |
1167 ms |
344456 KB |
Output is correct |
28 |
Correct |
1037 ms |
360052 KB |
Output is correct |
29 |
Correct |
1038 ms |
368524 KB |
Output is correct |
30 |
Correct |
1084 ms |
376920 KB |
Output is correct |
31 |
Correct |
1217 ms |
385416 KB |
Output is correct |
32 |
Correct |
1207 ms |
385416 KB |
Output is correct |
33 |
Correct |
1315 ms |
385416 KB |
Output is correct |
34 |
Correct |
532 ms |
385416 KB |
Output is correct |
35 |
Correct |
1274 ms |
406320 KB |
Output is correct |
36 |
Correct |
1282 ms |
409088 KB |
Output is correct |
37 |
Correct |
1279 ms |
422428 KB |
Output is correct |
38 |
Correct |
1279 ms |
427192 KB |
Output is correct |
39 |
Correct |
1226 ms |
440892 KB |
Output is correct |
40 |
Correct |
1161 ms |
453224 KB |
Output is correct |
41 |
Correct |
1309 ms |
456948 KB |
Output is correct |
42 |
Correct |
1195 ms |
459992 KB |
Output is correct |
43 |
Correct |
1326 ms |
483160 KB |
Output is correct |
44 |
Correct |
1267 ms |
485060 KB |
Output is correct |
45 |
Correct |
1164 ms |
492172 KB |
Output is correct |
46 |
Correct |
1175 ms |
500816 KB |
Output is correct |
47 |
Correct |
1082 ms |
517756 KB |
Output is correct |
48 |
Runtime error |
1130 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
49 |
Halted |
0 ms |
0 KB |
- |