답안 #546528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546528	2022-04-07T18:12:46 Z	inksamurai	Jail (JOI22_jail)	C++17	5 / 100	2597 ms	457340 KB

jail

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3x2WzQf ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
 
void slv(){
	int n;
	cin>>n;
	
	vec(vi) adj(n);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	int m;
	cin>>m;
	vec(pii) rbts;
	rep(i,m){
		int s,t;
		cin>>s>>t;
		s-=1,t-=1;
		rbts.pb({s,t});
	}

	// fill depth
	vi parent(n,0),depth(n,0),tin(n,0),tout(n,0);
	int tmer=0;
	{
		auto dfs=[&](auto self,int v,int par)->void{
			tin[v]=tmer++;
			for(auto u:adj[v]){
				if(u==par) continue;
				parent[u]=v;
				depth[u]=depth[v]+1;
				self(self,u,v);
			}
			tout[v]=tmer++;
		};
		dfs(dfs,0,-1);
	}

	// fill sparse table
	vec(vi) spr(18,vi(n)),ids,iids;
	ids=iids=spr;
	vi d0(n),d1(n);
	{
		rep(j,18){
			rep(v,n){
				spr[j][v]=!j?parent[v]:spr[j-1][spr[j-1][v]];
			}
		}
		int num=0;
		rep(v,n){
			d0[v]=num++;
		}
		rep(v,n){
			d1[v]=num++;
		}
		rep(t,2){
			rep(j,18){
				rep(v,n){
					if(!t) ids[j][v]=num++;
					else iids[j][v]=num++;
				}
			}
		}
		// print(num);
	}

	// add corressponding edges to it's ranges
	vec(vi) gph(50*n+m);
	rep(v,n){
		int up=spr[0][v];
		gph[d0[up]].pb(ids[0][v]);
		gph[d0[v]].pb(ids[0][v]);
		gph[iids[0][v]].pb(d1[up]);
		gph[iids[0][v]].pb(d1[v]);
	}
	rep(j,17){
		rep(v,n){
			int up=ids[j+1][v]; // next level node
			gph[ids[j][v]].pb(up);
			int par=ids[j][spr[j][v]]; // vertex after jump
			gph[par].pb(up);
			// if(v==2 and j==0) print(ids[j][v],ids[j][spr[j][v]],up);

			int iup=iids[j+1][v]; // next level inversed node
			gph[iup].pb(iids[j][v]);
			par=iids[j][spr[j][v]]; // vertex after jump
			gph[iup].pb(par);
		}
	}

	// debug junk
	{
		// // 0 1 2 3 4 5 6 7 
		// // 8 9 10 11 12 13 14 15 
		// // 16 17 18 19 20 21 22 23 

		// rep(j,2){
		// 	rep(v,n){
		// 		if(j==1){
		// 			cout<<ids[j][v]<<"\n";
		// 			for(auto u:gph[ids[j][v]]){
		// 				cout<<u<<" ";
		// 			}
		// 			cout<<"\n";
		// 		}
		// 		// cout<<ids[j][v]<<" ";
		// 	}

		// 	cout<<"\n";
		// }
	}

	auto ancestor=[&](int u,int v)->bool{
		return tin[u]<=tin[v] and tout[v]<=tout[u];
	};

	auto lca=[&](int s,int t)->int{
		if(ancestor(s,t)) return s;
		if(ancestor(t,s)) return t;
		int u=t;
		per(j,17){
			if(!ancestor(spr[j][u],s)){
				u=spr[j][u];
			}
		}
		return spr[0][u];
	};

	rep(i,m){
		auto [s,t]=rbts[i];
		int now_id=50*n+i;
		gph[now_id].pb(d0[s]);
		gph[d1[t]].pb(now_id);
	}

	auto add_edge=[&](int v,int up,int id){
		per(j,17){
			int u=spr[j][v];
			if(depth[u]>=depth[up]){
				gph[ids[j][v]].pb(id);
				gph[id].pb(iids[j][v]);
				v=u;
			}
		}
	};

	// for(auto u:gph[1]){
	// 	print(u);
	// }

	vi ss(n,-1),tt(n,-1);
	rep(i,m){
		auto [s,t]=rbts[i];
		ss[s]=50*n+i;
		tt[t]=50*n+i;
	}

	rep(i,m){
		auto [s,t]=rbts[i];
		int anc=lca(s,t);
		int now_id=50*n+i;
		if(tt[s]!=-1){
			// print(tt[s]);
			gph[now_id].pb(tt[s]);
		}
		if(ss[t]!=-1){
			// print(ss[t]);
			gph[ss[t]].pb(now_id);
		}
		if(ancestor(s,t) or ancestor(t,s)){
			if(ancestor(t,s)) swap(s,t);
			// print("here");
			t=spr[0][t];
			int id=now_id,up=s;
			int v=t;
			if(s!=t){
				// print(d0[t],id);
				// print(id,d1[t]);
				gph[d0[t]].pb(id);
				gph[id].pb(d1[t]);
			}
			per(j,17){
				int u=spr[j][v];
				if(depth[u]>depth[up]){
					// print(v,u,j,ids[j][v],id);
					// print(v,u,s,t,j,ids[j+1][v],id);
					gph[ids[j][v]].pb(id);
					gph[id].pb(iids[j][v]);
					v=u;
				}
			}
		}else{
			// print("here");
			if(depth[s]-depth[anc]>=2){
				s=spr[0][s];
				add_edge(s,anc,now_id);
			}
			if(depth[t]-depth[anc]>=2){
				t=spr[0][t];
				add_edge(t,anc,now_id);
			}
		}
	}

	auto has_cyc=[&]()->bool{
		vi usd(50*n+m,0),usd1(50*n+m,0);
		bool cyc=0;
		auto dfs=[&](auto self,int v)->void{
			usd[v]=1;
			usd1[v]=1;
			// print(v);
			for(auto u:gph[v]){
				if(usd1[u]){
					// print(u,v);
					cyc=1;
				}
				if(!usd[u]){
					self(self,u);
				}
			}
			usd1[v]=0;
		};
		// dfs(dfs,0);
		rep(v,50*n+m){
			if(!usd[v]){
				dfs(dfs,v);
			}
		}
		return cyc;
	};

	int res=has_cyc();
	// print(res);
	print(res?"No":"Yes");
}
 
signed main(){
_3x2WzQf;
	int t;
	cin>>t;
	rep(cs,t){
		slv();
	}
//	
	return 0;
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	212 ms	704 KB	Output is correct
5	Correct	413 ms	684 KB	Output is correct
6	Correct	20 ms	1068 KB	Output is correct
7	Correct	25 ms	1108 KB	Output is correct
8	Correct	20 ms	1116 KB	Output is correct
9	Correct	600 ms	18860 KB	Output is correct
10	Correct	726 ms	367152 KB	Output is correct
11	Correct	87 ms	396 KB	Output is correct
12	Correct	467 ms	1032 KB	Output is correct
13	Correct	776 ms	374108 KB	Output is correct
14	Correct	878 ms	374172 KB	Output is correct
15	Correct	1758 ms	401992 KB	Output is correct
16	Correct	2597 ms	457340 KB	Output is correct
17	Correct	767 ms	377664 KB	Output is correct
18	Correct	738 ms	379028 KB	Output is correct
19	Correct	748 ms	377708 KB	Output is correct
20	Correct	750 ms	377692 KB	Output is correct
21	Correct	1105 ms	401032 KB	Output is correct
22	Correct	832 ms	373076 KB	Output is correct

Subtask #2

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	19 ms	1200 KB	Output is correct
4	Correct	27 ms	1068 KB	Output is correct
5	Correct	20 ms	1220 KB	Output is correct
6	Correct	19 ms	1068 KB	Output is correct
7	Correct	19 ms	1068 KB	Output is correct
8	Correct	20 ms	1068 KB	Output is correct
9	Correct	22 ms	1092 KB	Output is correct
10	Correct	19 ms	1104 KB	Output is correct
11	Correct	16 ms	1100 KB	Output is correct
12	Incorrect	9 ms	1108 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	19 ms	1200 KB	Output is correct
4	Correct	27 ms	1068 KB	Output is correct
5	Correct	20 ms	1220 KB	Output is correct
6	Correct	19 ms	1068 KB	Output is correct
7	Correct	19 ms	1068 KB	Output is correct
8	Correct	20 ms	1068 KB	Output is correct
9	Correct	22 ms	1092 KB	Output is correct
10	Correct	19 ms	1104 KB	Output is correct
11	Correct	16 ms	1100 KB	Output is correct
12	Incorrect	9 ms	1108 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	19 ms	1200 KB	Output is correct
4	Correct	27 ms	1068 KB	Output is correct
5	Correct	20 ms	1220 KB	Output is correct
6	Correct	19 ms	1068 KB	Output is correct
7	Correct	19 ms	1068 KB	Output is correct
8	Correct	20 ms	1068 KB	Output is correct
9	Correct	22 ms	1092 KB	Output is correct
10	Correct	19 ms	1104 KB	Output is correct
11	Correct	16 ms	1100 KB	Output is correct
12	Incorrect	9 ms	1108 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	19 ms	1200 KB	Output is correct
4	Correct	27 ms	1068 KB	Output is correct
5	Correct	20 ms	1220 KB	Output is correct
6	Correct	19 ms	1068 KB	Output is correct
7	Correct	19 ms	1068 KB	Output is correct
8	Correct	20 ms	1068 KB	Output is correct
9	Correct	22 ms	1092 KB	Output is correct
10	Correct	19 ms	1104 KB	Output is correct
11	Correct	16 ms	1100 KB	Output is correct
12	Incorrect	9 ms	1108 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #6

0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	95 ms	384 KB	Output is correct
6	Incorrect	11 ms	1068 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #7

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	212 ms	704 KB	Output is correct
5	Correct	413 ms	684 KB	Output is correct
6	Correct	20 ms	1068 KB	Output is correct
7	Correct	25 ms	1108 KB	Output is correct
8	Correct	20 ms	1116 KB	Output is correct
9	Correct	600 ms	18860 KB	Output is correct
10	Correct	726 ms	367152 KB	Output is correct
11	Correct	87 ms	396 KB	Output is correct
12	Correct	467 ms	1032 KB	Output is correct
13	Correct	776 ms	374108 KB	Output is correct
14	Correct	878 ms	374172 KB	Output is correct
15	Correct	1758 ms	401992 KB	Output is correct
16	Correct	2597 ms	457340 KB	Output is correct
17	Correct	767 ms	377664 KB	Output is correct
18	Correct	738 ms	379028 KB	Output is correct
19	Correct	748 ms	377708 KB	Output is correct
20	Correct	750 ms	377692 KB	Output is correct
21	Correct	1105 ms	401032 KB	Output is correct
22	Correct	832 ms	373076 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	19 ms	1200 KB	Output is correct
26	Correct	27 ms	1068 KB	Output is correct
27	Correct	20 ms	1220 KB	Output is correct
28	Correct	19 ms	1068 KB	Output is correct
29	Correct	19 ms	1068 KB	Output is correct
30	Correct	20 ms	1068 KB	Output is correct
31	Correct	22 ms	1092 KB	Output is correct
32	Correct	19 ms	1104 KB	Output is correct
33	Correct	16 ms	1100 KB	Output is correct
34	Incorrect	9 ms	1108 KB	Output isn't correct
35	Halted	0 ms	0 KB	-