oj.uz

Submission #858348

# Submission time Handle Problem Language Result Execution time Memory
858348 2023-10-08T08:24:10 Z willychan Jail (JOI22_jail) C++14
72 / 100
 5000 ms 583012 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
const int N = 120005;
int p[N][20];
vector<int> side[N];
vector<pair<int,int> > qu;
pair<int,int> dep[N];
int n;
int t;
bool vis[N];
int dtime[N];
int t2;
void dfs(int cur){
	dep[cur].first=++t;
	for(auto i : side[cur])	{
		if(p[i][0]) continue;
		p[i][0]=cur;
		dfs(i);
	}
	dep[cur].second=++t;
}
vector<int> fe[N];

bool isanc(int a,int b){
	return (dep[a].first<dep[b].first && dep[a].second>dep[b].second);
}

int lca(int a,int b){
	if(isanc(a,b)) return a;
	if(isanc(b,a)) return b;
	for(int j=19;j>=0;j--){
		if(!isanc(p[b][j],a)) b = p[b][j];
	}
	return p[b][0];
}
vector<int> to[N];
vector<int> from[N];
bool inpath(int a,int b,int u){
	int c = lca(a,b);
	if(a==u || b==u || c==u) return 1;
	if((isanc(u,b)||isanc(u,a)) && isanc(c,u)) return 1;
	return 0;
}

void builtdep(int cur){
	vis[cur]=1;
	for(auto i : fe[cur]){
		if(!vis[i]) builtdep(i);
	}
	dtime[cur]=++t2;
}

void solve(){
	cin>>n;
	//clean up
	for(int i=1;i<=n;i++){
		side[i].clear();
		fe[i].clear();
		for(int j=0;j<20;j++) p[i][j]=0;
		qu.clear();
		dep[i] = {0,0};
		t = 0 ;
		t2=0;
		vis[i]=0;
		dtime[i]=0;
		to[i].clear();
		from[i].clear();
	}
	// built tree
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		side[a].push_back(b);
		side[b].push_back(a);
	}
	for(int j=0;j<20;j++) p[1][j]=1;
	dfs(1);

	int m;
	cin>>m;
	qu.resize(m+1);
	for(int i=1;i<=m;i++) cin>>qu[i].first>>qu[i].second;
	for(int i=1;i<=m;i++){
		to[qu[i].first].push_back(i);
		from[qu[i].second].push_back(i);
	}
	for(int i=1;i<=m;i++){
		int a = qu[i].first;
		int b = qu[i].second;
		while(a!=b){
			if(isanc(b,a)) swap(a,b);
			for(auto k : to[b]){
				fe[k].push_back(i);
			}
			for(auto k : from[b]){
				fe[i].push_back(k);
			}
			b = p[b][0];
		}
			for(auto k : to[b]){
				fe[k].push_back(i);
			}
			for(auto k : from[b]){
				fe[i].push_back(k);
			}
	}

	for(int i=1;i<=m;i++){
		if(!vis[i]) builtdep(i);
	}
	for(int i=1;i<=m;i++){
		for(auto e : fe[i]){
			if(dtime[e]>dtime[i]){
				cout<<"No\n";
				return ;
			}
		}
	}
	cout<<"Yes\n";
	return ;
		
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int q;cin>>q;
	while(q--){
		solve();
	}

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14964 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 8 ms 15196 KB Output is correct
5 Correct 15 ms 15484 KB Output is correct
6 Correct 5 ms 15012 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 5 ms 14936 KB Output is correct
9 Correct 82 ms 18512 KB Output is correct
10 Correct 443 ms 36252 KB Output is correct
11 Correct 6 ms 14940 KB Output is correct
12 Correct 32 ms 15868 KB Output is correct
13 Correct 121 ms 68744 KB Output is correct
14 Correct 161 ms 82644 KB Output is correct
15 Execution timed out 5069 ms 583012 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 4 ms 14972 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 4 ms 15052 KB Output is correct
11 Correct 3 ms 15032 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 4 ms 14972 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 4 ms 15052 KB Output is correct
11 Correct 3 ms 15032 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 2 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 4 ms 15020 KB Output is correct
17 Correct 4 ms 14940 KB Output is correct
18 Correct 4 ms 15052 KB Output is correct
19 Correct 4 ms 15196 KB Output is correct
20 Correct 3 ms 14940 KB Output is correct
21 Correct 4 ms 14940 KB Output is correct
22 Correct 3 ms 14936 KB Output is correct
23 Correct 4 ms 15004 KB Output is correct
24 Correct 4 ms 14940 KB Output is correct
25 Correct 3 ms 15052 KB Output is correct
26 Correct 3 ms 15012 KB Output is correct
27 Correct 3 ms 14940 KB Output is correct
28 Correct 3 ms 14940 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 4 ms 14972 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 4 ms 15052 KB Output is correct
11 Correct 3 ms 15032 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 2 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 4 ms 15020 KB Output is correct
17 Correct 4 ms 14940 KB Output is correct
18 Correct 4 ms 15052 KB Output is correct
19 Correct 4 ms 15196 KB Output is correct
20 Correct 3 ms 14940 KB Output is correct
21 Correct 4 ms 14940 KB Output is correct
22 Correct 3 ms 14936 KB Output is correct
23 Correct 4 ms 15004 KB Output is correct
24 Correct 4 ms 14940 KB Output is correct
25 Correct 3 ms 15052 KB Output is correct
26 Correct 3 ms 15012 KB Output is correct
27 Correct 3 ms 14940 KB Output is correct
28 Correct 3 ms 14940 KB Output is correct
29 Correct 4 ms 14936 KB Output is correct
30 Correct 4 ms 14940 KB Output is correct
31 Correct 5 ms 15112 KB Output is correct
32 Correct 4 ms 15016 KB Output is correct
33 Correct 5 ms 15196 KB Output is correct
34 Correct 4 ms 14940 KB Output is correct
35 Correct 4 ms 14940 KB Output is correct
36 Correct 3 ms 15192 KB Output is correct
37 Correct 4 ms 14940 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 4 ms 14972 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 4 ms 15052 KB Output is correct
11 Correct 3 ms 15032 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 2 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 4 ms 15020 KB Output is correct
17 Correct 4 ms 14940 KB Output is correct
18 Correct 4 ms 15052 KB Output is correct
19 Correct 4 ms 15196 KB Output is correct
20 Correct 3 ms 14940 KB Output is correct
21 Correct 4 ms 14940 KB Output is correct
22 Correct 3 ms 14936 KB Output is correct
23 Correct 4 ms 15004 KB Output is correct
24 Correct 4 ms 14940 KB Output is correct
25 Correct 3 ms 15052 KB Output is correct
26 Correct 3 ms 15012 KB Output is correct
27 Correct 3 ms 14940 KB Output is correct
28 Correct 3 ms 14940 KB Output is correct
29 Correct 4 ms 14936 KB Output is correct
30 Correct 4 ms 14940 KB Output is correct
31 Correct 5 ms 15112 KB Output is correct
32 Correct 4 ms 15016 KB Output is correct
33 Correct 5 ms 15196 KB Output is correct
34 Correct 4 ms 14940 KB Output is correct
35 Correct 4 ms 14940 KB Output is correct
36 Correct 3 ms 15192 KB Output is correct
37 Correct 4 ms 14940 KB Output is correct
38 Correct 79 ms 18356 KB Output is correct
39 Correct 397 ms 36240 KB Output is correct
40 Correct 57 ms 17444 KB Output is correct
41 Correct 29 ms 16528 KB Output is correct
42 Correct 37 ms 17492 KB Output is correct
43 Correct 18 ms 15964 KB Output is correct
44 Correct 8 ms 15412 KB Output is correct
45 Correct 39 ms 27484 KB Output is correct
46 Correct 40 ms 27512 KB Output is correct
47 Correct 87 ms 31056 KB Output is correct
48 Correct 90 ms 31468 KB Output is correct
49 Correct 43 ms 27456 KB Output is correct
50 Correct 43 ms 27480 KB Output is correct
51 Correct 34 ms 28680 KB Output is correct
52 Correct 45 ms 28576 KB Output is correct
53 Correct 9 ms 15704 KB Output is correct
54 Correct 40 ms 27216 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 15000 KB Output is correct
5 Correct 6 ms 15028 KB Output is correct
6 Correct 3 ms 15020 KB Output is correct
7 Correct 3 ms 14936 KB Output is correct
8 Correct 3 ms 14936 KB Output is correct
9 Correct 3 ms 15136 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 4 ms 14968 KB Output is correct
13 Correct 15 ms 15536 KB Output is correct
14 Correct 22 ms 15640 KB Output is correct
15 Correct 18 ms 15452 KB Output is correct
16 Correct 68 ms 28640 KB Output is correct
17 Correct 145 ms 40028 KB Output is correct
18 Correct 356 ms 66916 KB Output is correct
19 Correct 63 ms 30328 KB Output is correct
20 Correct 57 ms 30036 KB Output is correct
21 Correct 57 ms 30036 KB Output is correct
22 Correct 124 ms 39640 KB Output is correct
23 Correct 96 ms 39564 KB Output is correct
24 Correct 96 ms 39244 KB Output is correct
25 Correct 111 ms 39848 KB Output is correct
26 Correct 97 ms 39424 KB Output is correct
27 Correct 135 ms 43208 KB Output is correct
28 Correct 162 ms 47356 KB Output is correct
29 Correct 140 ms 44728 KB Output is correct
30 Correct 80 ms 36924 KB Output is correct
31 Correct 85 ms 37524 KB Output is correct
32 Correct 86 ms 36308 KB Output is correct
33 Correct 105 ms 37736 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14964 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 8 ms 15196 KB Output is correct
5 Correct 15 ms 15484 KB Output is correct
6 Correct 5 ms 15012 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 5 ms 14936 KB Output is correct
9 Correct 82 ms 18512 KB Output is correct
10 Correct 443 ms 36252 KB Output is correct
11 Correct 6 ms 14940 KB Output is correct
12 Correct 32 ms 15868 KB Output is correct
13 Correct 121 ms 68744 KB Output is correct
14 Correct 161 ms 82644 KB Output is correct
15 Execution timed out 5069 ms 583012 KB Time limit exceeded
16 Halted 0 ms 0 KB -