#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
struct SegTree {
int T=1;
vector<set<int>> t;
void build(int n) {
T=1;
while(T<=n) T*=2;
//cerr << "sz: "<< T<< "\n";
t.resize(2*T);
//cerr << "rozmiar: "<< sz(t) << "\n";
for(int i=0;i<2*T;i++) t[i].clear();
}
vector<int> query(int l, int r) {
l+=T, r+=T;
//cerr << "teraz: " << l << " " << r << "\n";
vector<int> ret;
for(int x:t[l]) ret.pb(x);
if(l!=r) for(int x:t[r]) ret.pb(x);
while(l/2!=r/2) {
if(l%2==0) for(int x:t[l+1]) ret.pb(x);
if(r%2==1) for(int x:t[r-1]) ret.pb(x);
l/=2;
r/=2;
}
return ret;
}
void add(int x, int val) {
x+=T;
while(x) {
t[x].insert(val);
x/=2;
}
}
void remove(int x, int val) {
x+=T;
while(x) {
t[x].erase(val);
x/=2;
}
}
};
struct SegTree2 {
int T = 1;
vector<set<int>> t;
void build(int n) {
T=1;
while(T<=n) T*=2;
t.resize(2*T);
for(int i=0;i<2*T;i++) t[i].clear();
}
void add(int l, int r, int val) {
l+=T, r+=T;
t[l].insert(val);
if(l!=r) t[r].insert(val);
while(l/2!=r/2) {
if(l%2==0) t[l+1].insert(val);
if(r%2==1) t[r-1].insert(val);
l/=2;
r/=2;
}
}
void remove(int l, int r, int val) {
l+=T, r+=T;
t[l].erase(val);
if(l!=r) t[r].insert(val);
while(l/2!=r/2) {
if(l%2==0) t[l+1].erase(val);
if(r%2==1) t[r-1].erase(val);
l/=2;
r/=2;
}
}
vector<int> query(int x) {
vector<int> ret;
x+=T;
while(x) {
for(int y:t[x]) ret.pb(y);
x/=2;
}
return ret;
}
};
vector<int> G[120009];
vector<int> G2[120009];
int tin[120009], tout[120009], T;
int jp2[120009][20];
int deg[120009];
pii tab[120009];
int col[120009];
int dep[120009];
int p[120009];
int heavy[120009];
int pos[120009], P;
int head[120009];
int dfs(int x, int y) {
p[x] = y;
dep[x] = dep[y]+1;
int sz = 1, max_sz=0;
tin[x] = ++T;
jp2[x][0] = y;
for(int i=1;i<20;i++) jp2[x][i] = jp2[jp2[x][i-1]][i-1];
for(int z:G[x]) if(z!=y) {
int c_sz = dfs(z, x);
//cout << x << " " << z << " " << c_sz << "\n";
//cout << max_sz << "\n";
sz += c_sz;
if(c_sz>max_sz) {
max_sz = c_sz;
//cout << "setting heavy to: " << z << "\n";
heavy[x] = z;
}
}
tout[x] = ++T;
return sz;
}
void decompose(int x, int h) {
head[x] = h;
pos[x] = ++P;
//cout << "pos: " << x << " " << pos[x] << "\n";
//cout << heavy[x] << "\n";
if(heavy[x]) {
decompose(heavy[x], h);
}
for(int y:G[x]) {
if(y!=p[x]&&y!=heavy[x]) decompose(y, y);
}
}
bool is_ancestor(int x, int y) {
return tin[x]<=tin[y]&&tout[x]>=tout[y];
}
int lca(int x, int y) {
if(is_ancestor(x, y)) return x;
if(is_ancestor(y, x)) return y;
for(int i=19;i>=0;i--) {
if(!is_ancestor(jp2[x][i], y)) {
x = jp2[x][i];
}
}
return jp2[x][0];
}
bool is_on_path(int x, int a, int b) {
return is_ancestor(a, x)&&is_ancestor(x, b);
}
bool f(int x, int a, int b) {
int y = lca(a, b);
//cerr << "lca: " << a << " " << b << " " << y << "\n";
//cerr << "checking: " << x << " " << a << " " << b << " " << (is_on_path(x, y, a)||is_on_path(x, y, b)) << "\n";
return is_on_path(x, y, a)||is_on_path(x, y, b);
}
SegTree seg1;
SegTree2 seg2;
vector<int> hld_query(int a, int b) {
//cout << "hld_query: " << a << " " << b << "\n";
vector<int> ret;
for (; head[a] != head[b]; b=p[head[b]]) {
if (dep[head[a]] > dep[head[b]]) swap(a, b);
for(int x:seg1.query(pos[head[b]], pos[b])) ret.pb(x);
}
if (dep[a] > dep[b]) swap(a, b);
for(int x:seg1.query(pos[a], pos[b])) ret.pb(x);
return ret;
}
void hld_add(int a, int b, int val) {
//cout << "hld_query: " << a << " " << b << "\n";
vector<int> ret;
for (; head[a] != head[b]; b=p[head[b]]) {
if (dep[head[a]] > dep[head[b]]) swap(a, b);
seg2.add(pos[head[b]], pos[b], val);
}
if (dep[a] > dep[b]) swap(a, b);
seg2.add(pos[a], pos[b], val);
}
void hld_remove(int a, int b, int val) {
//cout << "hld_query: " << a << " " << b << "\n";
vector<int> ret;
for (; head[a] != head[b]; b=p[head[b]]) {
if (dep[head[a]] > dep[head[b]]) swap(a, b);
seg2.remove(pos[head[b]], pos[b], val);
}
if (dep[a] > dep[b]) swap(a, b);
seg2.remove(pos[a], pos[b], val);
}
bool dfs2(int x) {
//cout << "dfs: " << x << "\n";
col[x] = 1;
vector<int> v1 = hld_query(tab[x].st, tab[x].nd);
for(int y:v1){
if(y==x) continue;
//cout << "sprawdzam1: "<< y << "\n";
if(col[y]==1) return false;
}
for(int y:v1) {
if(y==x) continue;
if(!dfs2(y)) return false;
}
//cout << "v2 dla: "<< tab[x].nd << "\n";
vector<int> v2 = seg2.query(pos[tab[x].nd]);
for(int y:v2) {
if(y==x) continue;
//cout << "sprawdzam2: "<< y << "\n";
if(col[y]==1) return false;
}
for(int y:v2) {
if(y==x) continue;
if(!dfs2(y)) return false;
}
col[x] = 2;
seg1.remove(pos[tab[x].st], x);
hld_remove(tab[x].st, tab[x].nd, x);
return true;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int q=1;
cin >> q;
while(q--) {
int n, m;
cin >> n;
for(int i=1;i<=n;i++) {
G[i].clear();
head[i] = 0;
heavy[i] = 0;
dep[i] = 0;
p[i] = 0;
}
for(int i=0;i<n-1;i++) {
int a, b;
cin >> a >> b;
G[a].pb(b);
G[b].pb(a);
}
tin[0] = T = 0;
dfs(1, 0);
P = 0;
decompose(1, 1);
tout[0] = T;
cin >> m;
for(int i=0;i<m;i++) {
G2[i].clear();
deg[i] = 0;
col[i] = 0;
}
seg1.build(n+9);
seg2.build(n+9);
for(int i=0;i<m;i++) {
cin >> tab[i].st >> tab[i].nd;
//cerr << pos[tab[i].st] << " " << tab[i].st << " " << tab[i].nd << "\n";
seg1.add(pos[tab[i].st], i);
hld_add(tab[i].st, tab[i].nd, i);
}
bool ans = true;
for(int i=0;i<m;i++) {
if(!col[i]) {
ans&=dfs2(i);
}
}
if(ans) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5972 KB |
Output is correct |
2 |
Correct |
3 ms |
5972 KB |
Output is correct |
3 |
Correct |
3 ms |
5972 KB |
Output is correct |
4 |
Correct |
18 ms |
6468 KB |
Output is correct |
5 |
Correct |
28 ms |
6852 KB |
Output is correct |
6 |
Correct |
4 ms |
6228 KB |
Output is correct |
7 |
Correct |
4 ms |
6228 KB |
Output is correct |
8 |
Correct |
9 ms |
6420 KB |
Output is correct |
9 |
Correct |
152 ms |
12760 KB |
Output is correct |
10 |
Correct |
147 ms |
72828 KB |
Output is correct |
11 |
Correct |
12 ms |
6100 KB |
Output is correct |
12 |
Correct |
100 ms |
7168 KB |
Output is correct |
13 |
Correct |
957 ms |
133796 KB |
Output is correct |
14 |
Correct |
363 ms |
138632 KB |
Output is correct |
15 |
Execution timed out |
5103 ms |
155616 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5972 KB |
Output is correct |
2 |
Correct |
4 ms |
5964 KB |
Output is correct |
3 |
Correct |
4 ms |
6228 KB |
Output is correct |
4 |
Correct |
4 ms |
6232 KB |
Output is correct |
5 |
Correct |
4 ms |
6228 KB |
Output is correct |
6 |
Correct |
4 ms |
6228 KB |
Output is correct |
7 |
Correct |
5 ms |
6228 KB |
Output is correct |
8 |
Correct |
4 ms |
6228 KB |
Output is correct |
9 |
Correct |
6 ms |
6236 KB |
Output is correct |
10 |
Correct |
4 ms |
6228 KB |
Output is correct |
11 |
Correct |
4 ms |
6228 KB |
Output is correct |
12 |
Correct |
3 ms |
6104 KB |
Output is correct |
13 |
Correct |
4 ms |
6104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5972 KB |
Output is correct |
2 |
Correct |
4 ms |
5964 KB |
Output is correct |
3 |
Correct |
4 ms |
6228 KB |
Output is correct |
4 |
Correct |
4 ms |
6232 KB |
Output is correct |
5 |
Correct |
4 ms |
6228 KB |
Output is correct |
6 |
Correct |
4 ms |
6228 KB |
Output is correct |
7 |
Correct |
5 ms |
6228 KB |
Output is correct |
8 |
Correct |
4 ms |
6228 KB |
Output is correct |
9 |
Correct |
6 ms |
6236 KB |
Output is correct |
10 |
Correct |
4 ms |
6228 KB |
Output is correct |
11 |
Correct |
4 ms |
6228 KB |
Output is correct |
12 |
Correct |
3 ms |
6104 KB |
Output is correct |
13 |
Correct |
4 ms |
6104 KB |
Output is correct |
14 |
Correct |
3 ms |
5960 KB |
Output is correct |
15 |
Correct |
4 ms |
5988 KB |
Output is correct |
16 |
Correct |
4 ms |
6248 KB |
Output is correct |
17 |
Correct |
4 ms |
6228 KB |
Output is correct |
18 |
Correct |
5 ms |
6244 KB |
Output is correct |
19 |
Correct |
4 ms |
5960 KB |
Output is correct |
20 |
Correct |
5 ms |
6240 KB |
Output is correct |
21 |
Correct |
4 ms |
6160 KB |
Output is correct |
22 |
Correct |
4 ms |
6228 KB |
Output is correct |
23 |
Correct |
3 ms |
5972 KB |
Output is correct |
24 |
Correct |
3 ms |
6092 KB |
Output is correct |
25 |
Correct |
4 ms |
6228 KB |
Output is correct |
26 |
Correct |
3 ms |
6096 KB |
Output is correct |
27 |
Correct |
4 ms |
6228 KB |
Output is correct |
28 |
Correct |
3 ms |
5964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5972 KB |
Output is correct |
2 |
Correct |
4 ms |
5964 KB |
Output is correct |
3 |
Correct |
4 ms |
6228 KB |
Output is correct |
4 |
Correct |
4 ms |
6232 KB |
Output is correct |
5 |
Correct |
4 ms |
6228 KB |
Output is correct |
6 |
Correct |
4 ms |
6228 KB |
Output is correct |
7 |
Correct |
5 ms |
6228 KB |
Output is correct |
8 |
Correct |
4 ms |
6228 KB |
Output is correct |
9 |
Correct |
6 ms |
6236 KB |
Output is correct |
10 |
Correct |
4 ms |
6228 KB |
Output is correct |
11 |
Correct |
4 ms |
6228 KB |
Output is correct |
12 |
Correct |
3 ms |
6104 KB |
Output is correct |
13 |
Correct |
4 ms |
6104 KB |
Output is correct |
14 |
Correct |
3 ms |
5960 KB |
Output is correct |
15 |
Correct |
4 ms |
5988 KB |
Output is correct |
16 |
Correct |
4 ms |
6248 KB |
Output is correct |
17 |
Correct |
4 ms |
6228 KB |
Output is correct |
18 |
Correct |
5 ms |
6244 KB |
Output is correct |
19 |
Correct |
4 ms |
5960 KB |
Output is correct |
20 |
Correct |
5 ms |
6240 KB |
Output is correct |
21 |
Correct |
4 ms |
6160 KB |
Output is correct |
22 |
Correct |
4 ms |
6228 KB |
Output is correct |
23 |
Correct |
3 ms |
5972 KB |
Output is correct |
24 |
Correct |
3 ms |
6092 KB |
Output is correct |
25 |
Correct |
4 ms |
6228 KB |
Output is correct |
26 |
Correct |
3 ms |
6096 KB |
Output is correct |
27 |
Correct |
4 ms |
6228 KB |
Output is correct |
28 |
Correct |
3 ms |
5964 KB |
Output is correct |
29 |
Correct |
10 ms |
6360 KB |
Output is correct |
30 |
Correct |
7 ms |
6228 KB |
Output is correct |
31 |
Correct |
6 ms |
6344 KB |
Output is correct |
32 |
Correct |
6 ms |
6232 KB |
Output is correct |
33 |
Correct |
4 ms |
6252 KB |
Output is correct |
34 |
Correct |
8 ms |
6176 KB |
Output is correct |
35 |
Correct |
13 ms |
6228 KB |
Output is correct |
36 |
Correct |
6 ms |
6232 KB |
Output is correct |
37 |
Correct |
7 ms |
6228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5972 KB |
Output is correct |
2 |
Correct |
4 ms |
5964 KB |
Output is correct |
3 |
Correct |
4 ms |
6228 KB |
Output is correct |
4 |
Correct |
4 ms |
6232 KB |
Output is correct |
5 |
Correct |
4 ms |
6228 KB |
Output is correct |
6 |
Correct |
4 ms |
6228 KB |
Output is correct |
7 |
Correct |
5 ms |
6228 KB |
Output is correct |
8 |
Correct |
4 ms |
6228 KB |
Output is correct |
9 |
Correct |
6 ms |
6236 KB |
Output is correct |
10 |
Correct |
4 ms |
6228 KB |
Output is correct |
11 |
Correct |
4 ms |
6228 KB |
Output is correct |
12 |
Correct |
3 ms |
6104 KB |
Output is correct |
13 |
Correct |
4 ms |
6104 KB |
Output is correct |
14 |
Correct |
3 ms |
5960 KB |
Output is correct |
15 |
Correct |
4 ms |
5988 KB |
Output is correct |
16 |
Correct |
4 ms |
6248 KB |
Output is correct |
17 |
Correct |
4 ms |
6228 KB |
Output is correct |
18 |
Correct |
5 ms |
6244 KB |
Output is correct |
19 |
Correct |
4 ms |
5960 KB |
Output is correct |
20 |
Correct |
5 ms |
6240 KB |
Output is correct |
21 |
Correct |
4 ms |
6160 KB |
Output is correct |
22 |
Correct |
4 ms |
6228 KB |
Output is correct |
23 |
Correct |
3 ms |
5972 KB |
Output is correct |
24 |
Correct |
3 ms |
6092 KB |
Output is correct |
25 |
Correct |
4 ms |
6228 KB |
Output is correct |
26 |
Correct |
3 ms |
6096 KB |
Output is correct |
27 |
Correct |
4 ms |
6228 KB |
Output is correct |
28 |
Correct |
3 ms |
5964 KB |
Output is correct |
29 |
Correct |
10 ms |
6360 KB |
Output is correct |
30 |
Correct |
7 ms |
6228 KB |
Output is correct |
31 |
Correct |
6 ms |
6344 KB |
Output is correct |
32 |
Correct |
6 ms |
6232 KB |
Output is correct |
33 |
Correct |
4 ms |
6252 KB |
Output is correct |
34 |
Correct |
8 ms |
6176 KB |
Output is correct |
35 |
Correct |
13 ms |
6228 KB |
Output is correct |
36 |
Correct |
6 ms |
6232 KB |
Output is correct |
37 |
Correct |
7 ms |
6228 KB |
Output is correct |
38 |
Correct |
113 ms |
12432 KB |
Output is correct |
39 |
Correct |
127 ms |
72140 KB |
Output is correct |
40 |
Correct |
89 ms |
10808 KB |
Output is correct |
41 |
Correct |
80 ms |
10808 KB |
Output is correct |
42 |
Correct |
93 ms |
11032 KB |
Output is correct |
43 |
Correct |
48 ms |
10060 KB |
Output is correct |
44 |
Correct |
49 ms |
7296 KB |
Output is correct |
45 |
Correct |
103 ms |
62200 KB |
Output is correct |
46 |
Correct |
101 ms |
62284 KB |
Output is correct |
47 |
Correct |
86 ms |
66520 KB |
Output is correct |
48 |
Correct |
93 ms |
66432 KB |
Output is correct |
49 |
Correct |
88 ms |
62472 KB |
Output is correct |
50 |
Correct |
102 ms |
62396 KB |
Output is correct |
51 |
Correct |
81 ms |
62744 KB |
Output is correct |
52 |
Correct |
87 ms |
62716 KB |
Output is correct |
53 |
Correct |
31 ms |
12700 KB |
Output is correct |
54 |
Correct |
123 ms |
62788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5972 KB |
Output is correct |
2 |
Correct |
3 ms |
5972 KB |
Output is correct |
3 |
Correct |
3 ms |
5972 KB |
Output is correct |
4 |
Correct |
3 ms |
5972 KB |
Output is correct |
5 |
Correct |
13 ms |
6188 KB |
Output is correct |
6 |
Correct |
3 ms |
6100 KB |
Output is correct |
7 |
Correct |
3 ms |
6100 KB |
Output is correct |
8 |
Correct |
3 ms |
5968 KB |
Output is correct |
9 |
Correct |
3 ms |
5972 KB |
Output is correct |
10 |
Correct |
3 ms |
6096 KB |
Output is correct |
11 |
Correct |
3 ms |
5972 KB |
Output is correct |
12 |
Correct |
6 ms |
6228 KB |
Output is correct |
13 |
Correct |
52 ms |
6720 KB |
Output is correct |
14 |
Correct |
82 ms |
7004 KB |
Output is correct |
15 |
Correct |
73 ms |
6872 KB |
Output is correct |
16 |
Correct |
313 ms |
78544 KB |
Output is correct |
17 |
Correct |
1257 ms |
159396 KB |
Output is correct |
18 |
Correct |
2904 ms |
260636 KB |
Output is correct |
19 |
Correct |
483 ms |
95432 KB |
Output is correct |
20 |
Correct |
463 ms |
95788 KB |
Output is correct |
21 |
Correct |
528 ms |
95900 KB |
Output is correct |
22 |
Correct |
1282 ms |
162324 KB |
Output is correct |
23 |
Correct |
649 ms |
162448 KB |
Output is correct |
24 |
Correct |
1266 ms |
163376 KB |
Output is correct |
25 |
Correct |
985 ms |
163664 KB |
Output is correct |
26 |
Correct |
1381 ms |
164176 KB |
Output is correct |
27 |
Correct |
2311 ms |
203908 KB |
Output is correct |
28 |
Correct |
1385 ms |
209940 KB |
Output is correct |
29 |
Correct |
1368 ms |
197092 KB |
Output is correct |
30 |
Correct |
982 ms |
137796 KB |
Output is correct |
31 |
Correct |
642 ms |
140196 KB |
Output is correct |
32 |
Correct |
981 ms |
135388 KB |
Output is correct |
33 |
Correct |
673 ms |
138400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5972 KB |
Output is correct |
2 |
Correct |
3 ms |
5972 KB |
Output is correct |
3 |
Correct |
3 ms |
5972 KB |
Output is correct |
4 |
Correct |
18 ms |
6468 KB |
Output is correct |
5 |
Correct |
28 ms |
6852 KB |
Output is correct |
6 |
Correct |
4 ms |
6228 KB |
Output is correct |
7 |
Correct |
4 ms |
6228 KB |
Output is correct |
8 |
Correct |
9 ms |
6420 KB |
Output is correct |
9 |
Correct |
152 ms |
12760 KB |
Output is correct |
10 |
Correct |
147 ms |
72828 KB |
Output is correct |
11 |
Correct |
12 ms |
6100 KB |
Output is correct |
12 |
Correct |
100 ms |
7168 KB |
Output is correct |
13 |
Correct |
957 ms |
133796 KB |
Output is correct |
14 |
Correct |
363 ms |
138632 KB |
Output is correct |
15 |
Execution timed out |
5103 ms |
155616 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |