#include "werewolf.h"
#include <cassert>
#include <algorithm>
#include <functional>
#include <numeric>
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
const int MN = 2e5+10;
const int MQ = 2e5+10;
struct DSU
{
int S;
std::vector<int> p;
DSU(int _S): S(_S), p(_S, -1) {}
int find(int n) {return p[n]==-1 ? n : p[n] = find(p[n]);}
bool merge(int a, int b) // b into a
{
a=find(a), b=find(b);
if(a==b) return 0;
p[b]=a; // no rank
return 1;
}
};
struct ST
{
public:
int S;
std::vector<int> v;
ST(int _S=0): S(_S), v(4*_S, -1) {}
void upd(int n, int l, int r, int q, int val)
{
if(r-l>1)
{
int m=l+(r-l)/2;
if(q < m) upd(n<<1, l, m, q, val);
else upd(n<<1|1, m, r, q, val);
v[n]=std::max(v[n<<1], v[n<<1|1]);
}
else
v[n]=val;
}
void upd(int q, int val) {upd(1, 0, S, q, val);}
int qry(int n, int l, int r, int ql, int qr)
{
if(ql <= l&&r <= qr) return v[n];
if(r-l>1)
{
int m=l+(r-l)/2, f=-1;
if(ql < m) ckmax(f, qry(n<<1, l, m, ql, qr));
if(m < qr) ckmax(f, qry(n<<1|1, m, r, ql, qr));
return f;
}
assert(0);
return -1;
}
int qry(int ql, int qr) {return qry(1, 0, S, ql, qr);}
};
int N, M, Q;
std::vector<int> a[MN], t[2][MN], ans, todo[MN];
int pre[2][MN], post[2][MN], ord[2][MN], ctr[2];
template<int T>
void dfs(int n, int p=-1)
{
ord[T][ctr[T]]=n;
pre[T][n]=ctr[T]++;
for(int x:t[T][n])
if(x!=p)
dfs<T>(x, n);
post[T][n]=ctr[T];
}
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) {
::N=N;
M=X.size();
Q=S.size();
ans.assign(Q, -1);
for(int i=0;i<M;++i)
{
a[X[i]].push_back(Y[i]);
a[Y[i]].push_back(X[i]);
}
std::vector<int> ss(Q, -1), es(Q, -1); // start/end subtrees
//human tree
{
std::vector<int> ord(Q);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int u, int v){return L[u]>L[v];});
DSU dsu(N);
for(int i=N-1, j=0;i>=0;--i)
{
for(int x:a[i])
{
int y=dsu.find(x);
if(i < x && dsu.merge(i, y))
t[0][i].push_back(y), t[0][y].push_back(i);
}
for(;j < Q && L[ord[j]]==i;++j)
ss[ord[j]]=dsu.find(S[ord[j]]);
}
}
//werewolf tree
{
std::vector<int> ord(Q);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int u, int v){return R[u]<R[v];});
DSU dsu(N);
for(int i=0, j=0;i<N;++i)
{
for(int x:a[i])
{
int y=dsu.find(x);
if(x < i && dsu.merge(i, y))
t[1][i].push_back(y), t[1][y].push_back(i);
}
for(;j < Q && R[ord[j]]==i;++j)
es[ord[j]]=dsu.find(E[ord[j]]);
}
}
dfs<0>(0);
dfs<1>(N-1);
for(int i=0;i<Q;++i)
todo[post[1][es[i]]].push_back(i);
ST segtree(N);
for(int i=0;i<N;++i)
{
segtree.upd(pre[0][ord[1][i]], i); // add ord[1][i]
for(int x:todo[i+1])
{
ans[x] = segtree.qry(pre[0][ss[x]], post[0][ss[x]]) >= pre[1][es[x]];
//printf("\t%d: %d\n", x, segtree.qry(pre[0][ss[x]], post[0][ss[x]]));
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
19020 KB |
Output is correct |
2 |
Correct |
12 ms |
19076 KB |
Output is correct |
3 |
Correct |
12 ms |
19008 KB |
Output is correct |
4 |
Correct |
12 ms |
19080 KB |
Output is correct |
5 |
Correct |
12 ms |
19016 KB |
Output is correct |
6 |
Correct |
13 ms |
19104 KB |
Output is correct |
7 |
Correct |
13 ms |
19020 KB |
Output is correct |
8 |
Correct |
13 ms |
19084 KB |
Output is correct |
9 |
Correct |
12 ms |
19056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
19020 KB |
Output is correct |
2 |
Correct |
12 ms |
19076 KB |
Output is correct |
3 |
Correct |
12 ms |
19008 KB |
Output is correct |
4 |
Correct |
12 ms |
19080 KB |
Output is correct |
5 |
Correct |
12 ms |
19016 KB |
Output is correct |
6 |
Correct |
13 ms |
19104 KB |
Output is correct |
7 |
Correct |
13 ms |
19020 KB |
Output is correct |
8 |
Correct |
13 ms |
19084 KB |
Output is correct |
9 |
Correct |
12 ms |
19056 KB |
Output is correct |
10 |
Correct |
19 ms |
19788 KB |
Output is correct |
11 |
Correct |
17 ms |
19788 KB |
Output is correct |
12 |
Correct |
19 ms |
19792 KB |
Output is correct |
13 |
Correct |
19 ms |
19980 KB |
Output is correct |
14 |
Correct |
18 ms |
19916 KB |
Output is correct |
15 |
Correct |
20 ms |
19944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
735 ms |
68676 KB |
Output is correct |
2 |
Correct |
623 ms |
71640 KB |
Output is correct |
3 |
Correct |
583 ms |
69280 KB |
Output is correct |
4 |
Correct |
597 ms |
68400 KB |
Output is correct |
5 |
Correct |
602 ms |
68472 KB |
Output is correct |
6 |
Correct |
645 ms |
68444 KB |
Output is correct |
7 |
Correct |
645 ms |
68408 KB |
Output is correct |
8 |
Correct |
547 ms |
71708 KB |
Output is correct |
9 |
Correct |
502 ms |
69276 KB |
Output is correct |
10 |
Correct |
529 ms |
68392 KB |
Output is correct |
11 |
Correct |
569 ms |
68336 KB |
Output is correct |
12 |
Correct |
584 ms |
68304 KB |
Output is correct |
13 |
Correct |
556 ms |
72848 KB |
Output is correct |
14 |
Correct |
564 ms |
72948 KB |
Output is correct |
15 |
Correct |
540 ms |
72992 KB |
Output is correct |
16 |
Correct |
576 ms |
72892 KB |
Output is correct |
17 |
Correct |
658 ms |
68648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
19020 KB |
Output is correct |
2 |
Correct |
12 ms |
19076 KB |
Output is correct |
3 |
Correct |
12 ms |
19008 KB |
Output is correct |
4 |
Correct |
12 ms |
19080 KB |
Output is correct |
5 |
Correct |
12 ms |
19016 KB |
Output is correct |
6 |
Correct |
13 ms |
19104 KB |
Output is correct |
7 |
Correct |
13 ms |
19020 KB |
Output is correct |
8 |
Correct |
13 ms |
19084 KB |
Output is correct |
9 |
Correct |
12 ms |
19056 KB |
Output is correct |
10 |
Correct |
19 ms |
19788 KB |
Output is correct |
11 |
Correct |
17 ms |
19788 KB |
Output is correct |
12 |
Correct |
19 ms |
19792 KB |
Output is correct |
13 |
Correct |
19 ms |
19980 KB |
Output is correct |
14 |
Correct |
18 ms |
19916 KB |
Output is correct |
15 |
Correct |
20 ms |
19944 KB |
Output is correct |
16 |
Correct |
735 ms |
68676 KB |
Output is correct |
17 |
Correct |
623 ms |
71640 KB |
Output is correct |
18 |
Correct |
583 ms |
69280 KB |
Output is correct |
19 |
Correct |
597 ms |
68400 KB |
Output is correct |
20 |
Correct |
602 ms |
68472 KB |
Output is correct |
21 |
Correct |
645 ms |
68444 KB |
Output is correct |
22 |
Correct |
645 ms |
68408 KB |
Output is correct |
23 |
Correct |
547 ms |
71708 KB |
Output is correct |
24 |
Correct |
502 ms |
69276 KB |
Output is correct |
25 |
Correct |
529 ms |
68392 KB |
Output is correct |
26 |
Correct |
569 ms |
68336 KB |
Output is correct |
27 |
Correct |
584 ms |
68304 KB |
Output is correct |
28 |
Correct |
556 ms |
72848 KB |
Output is correct |
29 |
Correct |
564 ms |
72948 KB |
Output is correct |
30 |
Correct |
540 ms |
72992 KB |
Output is correct |
31 |
Correct |
576 ms |
72892 KB |
Output is correct |
32 |
Correct |
658 ms |
68648 KB |
Output is correct |
33 |
Correct |
762 ms |
69976 KB |
Output is correct |
34 |
Correct |
370 ms |
53872 KB |
Output is correct |
35 |
Correct |
731 ms |
72388 KB |
Output is correct |
36 |
Correct |
741 ms |
69212 KB |
Output is correct |
37 |
Correct |
718 ms |
71616 KB |
Output is correct |
38 |
Correct |
756 ms |
69664 KB |
Output is correct |
39 |
Correct |
621 ms |
78116 KB |
Output is correct |
40 |
Correct |
760 ms |
77808 KB |
Output is correct |
41 |
Correct |
647 ms |
70740 KB |
Output is correct |
42 |
Correct |
610 ms |
68948 KB |
Output is correct |
43 |
Correct |
759 ms |
75900 KB |
Output is correct |
44 |
Correct |
678 ms |
71168 KB |
Output is correct |
45 |
Correct |
585 ms |
78332 KB |
Output is correct |
46 |
Correct |
576 ms |
78168 KB |
Output is correct |
47 |
Correct |
546 ms |
73060 KB |
Output is correct |
48 |
Correct |
548 ms |
72812 KB |
Output is correct |
49 |
Correct |
547 ms |
72672 KB |
Output is correct |
50 |
Correct |
559 ms |
73404 KB |
Output is correct |
51 |
Correct |
719 ms |
78308 KB |
Output is correct |
52 |
Correct |
749 ms |
78124 KB |
Output is correct |