답안 #546523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546523	2022-04-07T18:04:42 Z	inksamurai	Jail (JOI22_jail)	C++17	5 / 100	2284 ms	457284 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,m){
			int now_id=50*n+v;
			if(!usd[now_id]){
				dfs(dfs,now_id);
			}
		}
		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	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	175 ms	708 KB	Output is correct
5	Correct	389 ms	676 KB	Output is correct
6	Correct	18 ms	1068 KB	Output is correct
7	Correct	18 ms	1068 KB	Output is correct
8	Correct	18 ms	1120 KB	Output is correct
9	Correct	562 ms	18912 KB	Output is correct
10	Correct	564 ms	366956 KB	Output is correct
11	Correct	81 ms	340 KB	Output is correct
12	Correct	410 ms	808 KB	Output is correct
13	Correct	717 ms	374124 KB	Output is correct
14	Correct	808 ms	374192 KB	Output is correct
15	Correct	1598 ms	401920 KB	Output is correct
16	Correct	2284 ms	457284 KB	Output is correct
17	Correct	666 ms	377540 KB	Output is correct
18	Correct	642 ms	379200 KB	Output is correct
19	Correct	647 ms	377668 KB	Output is correct
20	Correct	658 ms	377660 KB	Output is correct
21	Correct	1012 ms	401132 KB	Output is correct
22	Correct	744 ms	372904 KB	Output is correct

Subtask #2

0 / 5.0

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

Subtask #3

0 / 16.0

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

Subtask #4

0 / 28.0

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

Subtask #5

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	17 ms	1108 KB	Output is correct
4	Correct	17 ms	1092 KB	Output is correct
5	Correct	17 ms	1100 KB	Output is correct
6	Correct	17 ms	1092 KB	Output is correct
7	Correct	18 ms	1104 KB	Output is correct
8	Correct	16 ms	1104 KB	Output is correct
9	Correct	19 ms	1068 KB	Output is correct
10	Correct	16 ms	1068 KB	Output is correct
11	Correct	14 ms	1092 KB	Output is correct
12	Incorrect	8 ms	1112 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	0 ms	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	78 ms	340 KB	Output is correct
6	Incorrect	8 ms	1108 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #7

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	175 ms	708 KB	Output is correct
5	Correct	389 ms	676 KB	Output is correct
6	Correct	18 ms	1068 KB	Output is correct
7	Correct	18 ms	1068 KB	Output is correct
8	Correct	18 ms	1120 KB	Output is correct
9	Correct	562 ms	18912 KB	Output is correct
10	Correct	564 ms	366956 KB	Output is correct
11	Correct	81 ms	340 KB	Output is correct
12	Correct	410 ms	808 KB	Output is correct
13	Correct	717 ms	374124 KB	Output is correct
14	Correct	808 ms	374192 KB	Output is correct
15	Correct	1598 ms	401920 KB	Output is correct
16	Correct	2284 ms	457284 KB	Output is correct
17	Correct	666 ms	377540 KB	Output is correct
18	Correct	642 ms	379200 KB	Output is correct
19	Correct	647 ms	377668 KB	Output is correct
20	Correct	658 ms	377660 KB	Output is correct
21	Correct	1012 ms	401132 KB	Output is correct
22	Correct	744 ms	372904 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	17 ms	1108 KB	Output is correct
26	Correct	17 ms	1092 KB	Output is correct
27	Correct	17 ms	1100 KB	Output is correct
28	Correct	17 ms	1092 KB	Output is correct
29	Correct	18 ms	1104 KB	Output is correct
30	Correct	16 ms	1104 KB	Output is correct
31	Correct	19 ms	1068 KB	Output is correct
32	Correct	16 ms	1068 KB	Output is correct
33	Correct	14 ms	1092 KB	Output is correct
34	Incorrect	8 ms	1112 KB	Output isn't correct
35	Halted	0 ms	0 KB	-