Submission #1244161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244161		nvujica	Jail (JOI22_jail)	C++20	0 / 100	5 ms	8772 KiB

jail

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 1.2e5 + 10;

int q, n, m;
int bio_cen[maxn];
vector <pair<int, int> > put[maxn];
vector <int> e[maxn];
int sz[maxn];
int bitce[maxn];
vector <int> v[maxn];
int vrh[maxn];
int indeg[maxn];
int bio[maxn];

void dfs(int x, int p){
	sz[x] = 1;
	
	for(auto x2: e[x]){
		if(x2 == p) continue;
		if(bio_cen[x2]) continue;
		
		dfs(x2, x);
		sz[x] += sz[x2];
	}
}

void dfs2(int x, int p){
	for(auto x2: e[x]){
		if(bio_cen[x2]) continue;
		if(x2 == p) continue;
		
		vrh[x2] = vrh[x];
		dfs2(x2, x);
	}
}

bool rek(int x, int ozn){
	bio[x] = ozn;
	
//	if(ozn == 2) cout << "x: " << x << endl;
	
	for(auto x2: v[x]){
//		if(x == 4 && ozn == 2) cout << x2 << " " << bio[x2] << endl;
		
		if(bio[x2] == ozn){
//			cout << "pa jesam" << endl;
//			cout << "ova dva " << x << ' ' << x2 << endl;

			return 0;
		}
		
		if(!bio[x2]){
			if(!rek(x2, ozn)) return 0;
		}
	}
	
	return 1;
}

bool calc(int cen){
	vrh[cen] = cen;
	
	for(auto x2: e[cen]){
		if(bio_cen[x2]) {
			vrh[x2] = x2;
		}
		
		vrh[x2] = x2;
		dfs2(x2, cen);
	}
	
	int otk = 0;
	
	for(auto x2: e[cen]){
		bio[x2] = 0;
		indeg[x2] = 0;
	}
	
	for(int i = 0; i < put[cen].size(); i++){
		int s = put[cen][i].fi;
		int t = put[cen][i].se;
		
		if(vrh[s] == vrh[t]) continue;
		if(vrh[s] == cen) continue;
		if(vrh[t] == cen) otk = vrh[s];
		
		v[vrh[s]].push_back(vrh[t]);
//		if(cen == 4) cout << "v " << vrh[s] << ' ' << vrh[t] << endl;
		
		indeg[vrh[t]]++;
	}
	
	if(indeg[otk]){
//		cout << "ovaj " << cen << ' ' << otk << endl;
		return 0;
	}
	
	int mini = 0;
	
	for(auto x2: e[cen]){
		sort(v[x2].begin(), v[x2].end());
		v[x2].erase(unique(v[x2].begin(), v[x2].end()), v[x2].end());
	}
	
	for(auto x2: e[cen]){
//		if(bio_cen[x2])

		if(bio[x2]) continue;
		if(indeg[x2]) continue;
		
		//if(cen == 1) cout << "krecem " << cen << ' ' << x2 << endl;
		
	 	if(!rek(x2, x2)) return 0;
	}
	
	for(auto x2: e[cen]){
		if(!bio[x2]){
			
//			if(cen == 1) cout << "tu " << x2 << endl;
			if(!rek(x2, x2)) return 0;
		}
	}
	
	for(auto x2: e[cen]){
		if(bio_cen[x2]) continue;
		
		v[x2].clear();
		indeg[x2] = 0;
	}
	
	return 1;
}

int nadji_cen(int poc){
	dfs(poc, 0);
		
//	cout << "gotov " << endl;
	
	int x = poc;	
	
	while(true){
		bool naso = 0;
		
//		cout << x << endl;
		
		for(auto x2: e[x]){
			if(bio_cen[x2]) continue;
//			if(x2 == p) continue;
			
			if(sz[x2] > sz[poc] / 2 && sz[x2] < sz[x]){
				x = x2;
				naso = 1;
				break;
			}
		}
		
		if(!naso) break;
	}
	
	return x;
}

bool centro(int cen){
	sort(put[cen].begin(), put[cen].end());
	put[cen].erase(unique(put[cen].begin(), put[cen].end()), put[cen].end());
	
//	cout << "centroid: " << cen << endl;
//	
//	cout << "putovi:" << endl;
//	for(int i = 0; i < put[cen].size(); i++){
//		cout << put[cen][i].fi << ' ' << put[cen][i].se << endl;
//	}
//	cout << endl;
//	cout << endl;
	
	if(!calc(cen)) return 0;
	
	bio_cen[cen] = 1;
	
	for(auto x2: e[cen]){
		if(bio_cen[x2]) continue;
		
//		for(int i = 0; i < e[x2].size(); i++){
//			if(e[x2][i] == cen){
//				e[x2].erase(e[x2].begin() + i);
//				break;
//			}
//		}
		
		bitce[x2] = nadji_cen(x2);
	}
	
	for(int i = 0; i < put[cen].size(); i++){
		int s = put[cen][i].fi;
		int t = put[cen][i].se;
		
		if(vrh[s] == vrh[t]) put[bitce[vrh[s]]].push_back({s, t});
		else {
			int a = vrh[s];
			int b = vrh[t];
			
			if(a != cen) put[bitce[a]].push_back({a, cen});
			if(b != cen) put[bitce[b]].push_back({cen, b});
		}
	}
	
	put[cen].clear();
	
	for(auto x2: e[cen]){
		if(bio_cen[x2]) continue;
		
		if(!centro(bitce[x2])) return 0;
	}
	
	return 1;
}

void solve(){
	cin >> n;
	
	for(int i = 0; i < n - 1; i++){
		int a, b;
		cin >> a >> b;
		
		e[a].push_back(b);
		e[b].push_back(a);
	}
	
	int cen = nadji_cen(1);
	
//	for(int i = 1; i <= n; i++){
//		cout << sz[i] << ' ';
//	}
//	cout << endl;
	
//	cout << "cen: " << cen << endl;
	
	cin >> m;
	
	for(int i = 0; i < m; i++){
		int s, t;
		cin >> s >> t;
		put[cen].push_back({s, t});
	}
	
	if(centro(cen)) cout << "Yes\n";
	else cout << "No\n";
//	cout << endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> q;
	
	while(q--){
		solve();
		
		for(int i = 1; i <= n; i++){
			e[i].clear();
			v[i].clear();
			vrh[i] = 0;
			bio[i] = 0;
			indeg[i] = 0;
			bitce[i] = 0;
			sz[i] = 0;
			put[i].clear();
			bio_cen[i] = 0;
		}
	}
	
//	vector <pair<int, int> > put[maxn];
//	vector <int> e[maxn];
//	int sz[maxn];
//	int bitce[maxn];
//	vector <int> v[maxn];
//	int vrh[maxn];
//	int indeg[maxn];
//	int bio[maxn];

	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23