oj.uz

Submission #552109

# Submission time Handle Problem Language Result Execution time Memory
552109 2022-04-22T12:33:46 Z errorgorn Jail (JOI22_jail) C++17
5 / 100
 207 ms 49960 KB 
// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,q;
vector<int> al[120005];
ii arr[120005];

int d[120005];
int tkd[120005][19];

void dfs(int i,int p){
	for (auto it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		int curr=tkd[it][0]=i;
		rep(x,0,19){
			if (curr==-1) continue;
			curr=tkd[it][x+1]=tkd[curr][x];
		}
		dfs(it,i);
	}
}

int mov(int i,int k){
	rep(x,0,19) if (k&(1<<x)) i=tkd[i][x];
	return i;
}

int lca(int i,int j){
	if (d[i]<d[j]) swap(i,j);
	i=mov(i,d[i]-d[j]);
	if (i==j) return i;
	
	rep(x,19,0) if (tkd[i][x]!=tkd[j][x]){
		i=tkd[i][x];
		j=tkd[j][x];
	}
	
	return tkd[i][0];
}

struct UFDS{
	int p[120005];
	
	void reset(int n){
		rep(x,1,n+1) p[x]=x;
	}
	
	int par(int i){
		if (p[i]==i) return i;
		else return p[i]=par(p[i]);
	}
	
	void unions(int i,int j){
		i=par(i),j=par(j);
		p[i]=j;
	}
} fwd,bwd;

vector<int> al2[120005];
bool vis[120005];
vector<int> topo;

void dfs_top(int i){
	vis[i]=true;
	for (auto it:al2[i]) if (!vis[it]) dfs_top(it);
	topo.pub(i);
}

int pos[120005];
bool good[120005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		
		rep(x,1,n+1) al[x].clear();
		
		int a,b;
		rep(x,1,n){
			cin>>a>>b;
			al[a].pub(b);
			al[b].pub(a);
		}
		
		rep(x,1,n+1) rep(y,0,19) tkd[x][y]=-1;
		dfs(1,-1);
		
		fwd.reset(n);
		bwd.reset(n);
		
		cin>>q;
		rep(x,0,q){
			cin>>a>>b;
			
			arr[x]={a,b};
			
			int g=lca(a,b);
			while (d[a]>d[g]){
				fwd.unions(a,tkd[a][0]);
				a=fwd.par(a);
			}
			while (b!=1 && d[b]>d[g]){
				bwd.unions(b,tkd[b][0]);
				b=bwd.par(b);
			}
		}
		
		bool ok=true;
		rep(x,1,n+1) al2[x].clear();
		rep(x,2,n+1){
			bool f=fwd.par(x)!=x;
			bool b=bwd.par(x)!=x;
			
			if (f && b) ok=false;
			if (f) al2[x].pub(tkd[x][0]);
			if (b) al2[tkd[x][0]].pub(x);
		}
		
		if (!ok){
			cout<<"No"<<endl;
			continue;
		}
		
		topo={-1};
		rep(x,1,n+1) vis[x]=false;
		rep(x,1,n+1) if (!vis[x]) dfs_top(x);
		
		//for (auto it:topo) cout<<it<<" "; cout<<endl;
		rep(x,1,n+1) pos[topo[x]]=x;
		
		rep(x,1,n+1) good[x]=true;
		rep(x,0,q) good[arr[x].se]=false;
		
		vector<int> idx;
		rep(x,0,q) idx.pub(x);
		sort(all(idx),[](int i,int j){
			return pos[arr[i].fi]>pos[arr[j].fi];
		});
		
		fwd.reset(n);
		rep(x,1,n+1) for (auto y:al[x]) if (good[x] && good[y]) fwd.unions(x,y);
		
		for (auto it:idx){
			int a=arr[it].fi,b=arr[it].se;
			//cout<<"debug: "<<a<<" "<<b<<endl;
			
			good[b]=true;
			for (auto it:al[b]) if (good[it]) fwd.unions(it,b);
			
			if (fwd.par(a)!=fwd.par(b)) ok=false;
		}
		
		if (ok) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 16 ms 5972 KB Output is correct
5 Correct 25 ms 6060 KB Output is correct
6 Correct 5 ms 6100 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 5 ms 5972 KB Output is correct
9 Correct 36 ms 8916 KB Output is correct
10 Correct 74 ms 44484 KB Output is correct
11 Correct 9 ms 6128 KB Output is correct
12 Correct 32 ms 6916 KB Output is correct
13 Correct 81 ms 46620 KB Output is correct
14 Correct 81 ms 44252 KB Output is correct
15 Correct 129 ms 43648 KB Output is correct
16 Correct 207 ms 45760 KB Output is correct
17 Correct 85 ms 47572 KB Output is correct
18 Correct 101 ms 49960 KB Output is correct
19 Correct 95 ms 47596 KB Output is correct
20 Correct 82 ms 44536 KB Output is correct
21 Correct 92 ms 44660 KB Output is correct
22 Correct 89 ms 47680 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 5 ms 6100 KB Output is correct
4 Incorrect 6 ms 6100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 5 ms 6100 KB Output is correct
4 Incorrect 6 ms 6100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 5 ms 6100 KB Output is correct
4 Incorrect 6 ms 6100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 5 ms 6100 KB Output is correct
4 Incorrect 6 ms 6100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5964 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 5 ms 5928 KB Output is correct
5 Correct 9 ms 6012 KB Output is correct
6 Incorrect 4 ms 6100 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 16 ms 5972 KB Output is correct
5 Correct 25 ms 6060 KB Output is correct
6 Correct 5 ms 6100 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 5 ms 5972 KB Output is correct
9 Correct 36 ms 8916 KB Output is correct
10 Correct 74 ms 44484 KB Output is correct
11 Correct 9 ms 6128 KB Output is correct
12 Correct 32 ms 6916 KB Output is correct
13 Correct 81 ms 46620 KB Output is correct
14 Correct 81 ms 44252 KB Output is correct
15 Correct 129 ms 43648 KB Output is correct
16 Correct 207 ms 45760 KB Output is correct
17 Correct 85 ms 47572 KB Output is correct
18 Correct 101 ms 49960 KB Output is correct
19 Correct 95 ms 47596 KB Output is correct
20 Correct 82 ms 44536 KB Output is correct
21 Correct 92 ms 44660 KB Output is correct
22 Correct 89 ms 47680 KB Output is correct
23 Correct 3 ms 5972 KB Output is correct
24 Correct 3 ms 5972 KB Output is correct
25 Correct 5 ms 6100 KB Output is correct
26 Incorrect 6 ms 6100 KB Output isn't correct
27 Halted 0 ms 0 KB -