oj.uz

Submission #674598

# Submission time Handle Problem Language Result Execution time Memory
674598 2022-12-25T09:36:43 Z amirhoseinfar1385 Jail (JOI22_jail) C++17
61 / 100
 5000 ms 37636 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=120000+5,maxl=19;
vector<int>adj[maxn];
int lca[maxl][maxn];
int high[maxn];
pair<int,int>allm[maxn];
pair<int,int>stf[maxn];
int n,m,timea=0;
set<int>adjdag[maxn];
void dfs(int u=1,int par=0){
	lca[0][u]=par;
	high[u]=high[par]+1;
	timea++;
	stf[u].first=timea;
	for(auto x:adj[u]){
		if(x!=par){
			dfs(x,u);
		}
	}
	timea++;
	stf[u].second=timea;
}

void callca(){
	for(int i=1;i<maxl;i++){
		for(int j=0;j<=n;j++){
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}

int getlca(int u,int v){
	if(u==v){
		return u;
	}
	if(high[u]<high[v]){
		swap(u,v);
	}
	for(int i=maxl-1;i>=0;i--){
		if(lca[i][u]==0){
			continue;
		}
		int pu=lca[i][u];
		if(!(stf[pu].first<=stf[v].first&&stf[pu].second>=stf[v].second)){
			u=pu;
		}
	}
	return lca[0][u];
}

int dis(int u,int v){
	int uv=getlca(u,v);
//	cout<<u<<" "<<v<<" >>- "<<uv<<endl;
	int ret=high[u]+high[v];
	ret-=high[uv]*2;
	return ret;
}

bool calin(int u,int v1,int v2){
	int uv1=dis(u,v1),uv2=dis(u,v2),v1v2=dis(v1,v2);
	if(uv1+uv2==v1v2){
//	    cout<<u<<" "<<v1<<" "<<v2<<endl;
		return 1;
	}
	else{
		return 0;
	}
}

void calad(int u,int v){
	int u1=allm[u].first,u2=allm[u].second,v1=allm[v].first,v2=allm[v].second;
	if(calin(v2,u1,u2)){
//	    cout<<u<<" 1 "<<v<<endl;
		adjdag[u].insert(v);
	}
	else if(calin(u1,v1,v2)){
//	    cout<<u<<" 2 "<<v<<endl;
		adjdag[u].insert(v);
	}
	if(calin(u2,v1,v2)){
//	    cout<<v<<" 3 "<<u<<endl;
		adjdag[v].insert(u);
	}
	else if(calin(v1,u1,u2)){
//	    cout<<v<<" 4 "<<u<<endl;
		adjdag[v].insert(u);
	}
}
int res;
void caldag(){
	vector<int>val(m);
	for(int i=0;i<m;i++){
		for(auto x:adjdag[i]){
//		    cout<<i<<" "<<x<<endl;
			val[x]++;
		}
	}
	vector<int>now;
	for(int i=0;i<m;i++){
		if(val[i]==0){
			res++;
			now.push_back(i);
		}
	}
	while((int)now.size()>0){
		int x=now.back();
		now.pop_back();
		for(auto y:adjdag[x]){
			val[y]--;
			if(val[y]==0){
				now.push_back(y);
				res++;
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int asd=0;asd<t;asd++){
		timea=0;
		for(int i=0;i<=n;i++){
			adj[i].clear();
			for(int j=0;j<maxl;j++){
				lca[j][i]=0;
			}
			high[i]=0;
			stf[i].first=stf[i].second=0;
		}
		for(int i=0;i<=m;i++){
			adjdag[i].clear();
		}
		cin>>n;
		for(int i=0;i<n-1;i++){
			int u,v;
			cin>>u>>v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		dfs();
		callca();
		//cout<<dis(8,4)<<" "<<dis(3,4)<<" "<<dis(8,3)<<endl;
		cin>>m;
		for(int i=0;i<m;i++){
			cin>>allm[i].first>>allm[i].second;
		}
		for(int i=0;i<m;i++){
			for(int j=i+1;j<m;j++){
				calad(i,j);
			}
		}
		res=0;
		caldag();
		if(res==m){
			cout<<"Yes\n";
		}
		else{
			cout<<"No\n";
		}
		res=0;
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 4 ms 8788 KB Output is correct
3 Correct 4 ms 8884 KB Output is correct
4 Correct 14 ms 9244 KB Output is correct
5 Correct 24 ms 9652 KB Output is correct
6 Correct 6 ms 8916 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 83 ms 9236 KB Output is correct
9 Correct 3093 ms 18332 KB Output is correct
10 Correct 145 ms 37556 KB Output is correct
11 Correct 27 ms 8916 KB Output is correct
12 Correct 838 ms 10396 KB Output is correct
13 Execution timed out 5042 ms 32912 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 4 ms 8788 KB Output is correct
3 Correct 5 ms 8920 KB Output is correct
4 Correct 5 ms 8916 KB Output is correct
5 Correct 5 ms 8920 KB Output is correct
6 Correct 6 ms 8916 KB Output is correct
7 Correct 6 ms 8924 KB Output is correct
8 Correct 6 ms 8916 KB Output is correct
9 Correct 7 ms 8900 KB Output is correct
10 Correct 5 ms 8916 KB Output is correct
11 Correct 6 ms 8916 KB Output is correct
12 Correct 5 ms 8920 KB Output is correct
13 Correct 5 ms 8916 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 4 ms 8788 KB Output is correct
3 Correct 5 ms 8920 KB Output is correct
4 Correct 5 ms 8916 KB Output is correct
5 Correct 5 ms 8920 KB Output is correct
6 Correct 6 ms 8916 KB Output is correct
7 Correct 6 ms 8924 KB Output is correct
8 Correct 6 ms 8916 KB Output is correct
9 Correct 7 ms 8900 KB Output is correct
10 Correct 5 ms 8916 KB Output is correct
11 Correct 6 ms 8916 KB Output is correct
12 Correct 5 ms 8920 KB Output is correct
13 Correct 5 ms 8916 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 7 ms 8776 KB Output is correct
16 Correct 6 ms 8916 KB Output is correct
17 Correct 6 ms 8916 KB Output is correct
18 Correct 6 ms 8916 KB Output is correct
19 Correct 5 ms 8788 KB Output is correct
20 Correct 5 ms 8916 KB Output is correct
21 Correct 7 ms 8864 KB Output is correct
22 Correct 5 ms 8920 KB Output is correct
23 Correct 5 ms 8788 KB Output is correct
24 Correct 5 ms 8788 KB Output is correct
25 Correct 5 ms 8916 KB Output is correct
26 Correct 5 ms 8860 KB Output is correct
27 Correct 5 ms 8916 KB Output is correct
28 Correct 5 ms 8784 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 4 ms 8788 KB Output is correct
3 Correct 5 ms 8920 KB Output is correct
4 Correct 5 ms 8916 KB Output is correct
5 Correct 5 ms 8920 KB Output is correct
6 Correct 6 ms 8916 KB Output is correct
7 Correct 6 ms 8924 KB Output is correct
8 Correct 6 ms 8916 KB Output is correct
9 Correct 7 ms 8900 KB Output is correct
10 Correct 5 ms 8916 KB Output is correct
11 Correct 6 ms 8916 KB Output is correct
12 Correct 5 ms 8920 KB Output is correct
13 Correct 5 ms 8916 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 7 ms 8776 KB Output is correct
16 Correct 6 ms 8916 KB Output is correct
17 Correct 6 ms 8916 KB Output is correct
18 Correct 6 ms 8916 KB Output is correct
19 Correct 5 ms 8788 KB Output is correct
20 Correct 5 ms 8916 KB Output is correct
21 Correct 7 ms 8864 KB Output is correct
22 Correct 5 ms 8920 KB Output is correct
23 Correct 5 ms 8788 KB Output is correct
24 Correct 5 ms 8788 KB Output is correct
25 Correct 5 ms 8916 KB Output is correct
26 Correct 5 ms 8860 KB Output is correct
27 Correct 5 ms 8916 KB Output is correct
28 Correct 5 ms 8784 KB Output is correct
29 Correct 78 ms 9204 KB Output is correct
30 Correct 27 ms 8916 KB Output is correct
31 Correct 32 ms 9048 KB Output is correct
32 Correct 18 ms 8916 KB Output is correct
33 Correct 8 ms 8916 KB Output is correct
34 Correct 42 ms 8992 KB Output is correct
35 Correct 60 ms 9180 KB Output is correct
36 Correct 36 ms 8916 KB Output is correct
37 Correct 29 ms 8968 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 4 ms 8788 KB Output is correct
3 Correct 5 ms 8920 KB Output is correct
4 Correct 5 ms 8916 KB Output is correct
5 Correct 5 ms 8920 KB Output is correct
6 Correct 6 ms 8916 KB Output is correct
7 Correct 6 ms 8924 KB Output is correct
8 Correct 6 ms 8916 KB Output is correct
9 Correct 7 ms 8900 KB Output is correct
10 Correct 5 ms 8916 KB Output is correct
11 Correct 6 ms 8916 KB Output is correct
12 Correct 5 ms 8920 KB Output is correct
13 Correct 5 ms 8916 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 7 ms 8776 KB Output is correct
16 Correct 6 ms 8916 KB Output is correct
17 Correct 6 ms 8916 KB Output is correct
18 Correct 6 ms 8916 KB Output is correct
19 Correct 5 ms 8788 KB Output is correct
20 Correct 5 ms 8916 KB Output is correct
21 Correct 7 ms 8864 KB Output is correct
22 Correct 5 ms 8920 KB Output is correct
23 Correct 5 ms 8788 KB Output is correct
24 Correct 5 ms 8788 KB Output is correct
25 Correct 5 ms 8916 KB Output is correct
26 Correct 5 ms 8860 KB Output is correct
27 Correct 5 ms 8916 KB Output is correct
28 Correct 5 ms 8784 KB Output is correct
29 Correct 78 ms 9204 KB Output is correct
30 Correct 27 ms 8916 KB Output is correct
31 Correct 32 ms 9048 KB Output is correct
32 Correct 18 ms 8916 KB Output is correct
33 Correct 8 ms 8916 KB Output is correct
34 Correct 42 ms 8992 KB Output is correct
35 Correct 60 ms 9180 KB Output is correct
36 Correct 36 ms 8916 KB Output is correct
37 Correct 29 ms 8968 KB Output is correct
38 Correct 3086 ms 18280 KB Output is correct
39 Correct 156 ms 37636 KB Output is correct
40 Correct 2141 ms 14224 KB Output is correct
41 Correct 1201 ms 10804 KB Output is correct
42 Correct 1509 ms 14804 KB Output is correct
43 Correct 52 ms 10828 KB Output is correct
44 Correct 951 ms 9584 KB Output is correct
45 Correct 158 ms 24484 KB Output is correct
46 Correct 145 ms 24340 KB Output is correct
47 Correct 390 ms 28048 KB Output is correct
48 Correct 369 ms 28164 KB Output is correct
49 Correct 244 ms 24524 KB Output is correct
50 Correct 254 ms 24492 KB Output is correct
51 Correct 87 ms 25520 KB Output is correct
52 Correct 95 ms 25560 KB Output is correct
53 Correct 733 ms 10112 KB Output is correct
54 Correct 155 ms 24296 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 5 ms 8788 KB Output is correct
3 Correct 4 ms 8788 KB Output is correct
4 Correct 4 ms 8776 KB Output is correct
5 Correct 27 ms 8916 KB Output is correct
6 Correct 5 ms 9044 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 5 ms 8788 KB Output is correct
9 Correct 5 ms 8788 KB Output is correct
10 Correct 6 ms 8788 KB Output is correct
11 Correct 5 ms 8788 KB Output is correct
12 Correct 37 ms 8976 KB Output is correct
13 Correct 434 ms 9484 KB Output is correct
14 Correct 228 ms 9924 KB Output is correct
15 Correct 314 ms 9548 KB Output is correct
16 Execution timed out 5054 ms 25020 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 4 ms 8788 KB Output is correct
3 Correct 4 ms 8884 KB Output is correct
4 Correct 14 ms 9244 KB Output is correct
5 Correct 24 ms 9652 KB Output is correct
6 Correct 6 ms 8916 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 83 ms 9236 KB Output is correct
9 Correct 3093 ms 18332 KB Output is correct
10 Correct 145 ms 37556 KB Output is correct
11 Correct 27 ms 8916 KB Output is correct
12 Correct 838 ms 10396 KB Output is correct
13 Execution timed out 5042 ms 32912 KB Time limit exceeded
14 Halted 0 ms 0 KB -