Submission #891068

#	Time	Username	Problem	Language	Result	Execution time	Memory
891068		iskhakkutbilim	Jail (JOI22_jail)	C++17	0 / 100	0 ms	348 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 120000;




void solve(){
	 int n;cin >> n;
	 vector< vector<pair<int, int> > > g(n+1);
	 vector<int> edge1(n+1, 0), edge2(n+1, 0);
	 vector<int> par_index(n+1, 0);
	for(int i = 1;i < n; i++){
		int a, b; cin >> a >> b;
		g[a].push_back({b, i});
		g[b].push_back({a, i});
	}
	int q; cin >> q;
	vector< pair<int, int> > query(q);
	for(int i = 0;i < q; i++){
		cin >> query[i].ff >> query[i].ss;
	}
	vector<int> sub(n + 1, 0), depth(n + 1, 0);
	vector<int> tin(n + 1), tout(n + 1);
	int timer = 1;
	int up[n+1][18];
	function<void(int, int)> dfs=[&](int v, int par){
		tin[v] = timer++;
		up[v][0] = par;
		for(int j = 1;j < 18; j++){
			up[v][j] = up[up[v][j-1]][j-1];
		}
		sub[v]+= 1;
		for(auto [to, idx] : g[v]){
			if(to == par) continue;
			depth[to] = depth[v] + 1;
			par_index[to] = idx;
			dfs(to, v);
			sub[v]+= sub[to];
		}
		tout[v] = timer;
	};	
	dfs(1, 1);
	auto lca = [&](int a, int b){
		if(depth[a] > depth[b]) swap(a, b);
		int k = depth[b] - depth[a];
		for(int i = 0;i < 18; i++){
			if(k & (1<<i)){
				b = up[b][i];
			}
		}
		if(a == b) return a;
		for(int i = 17; i >= 0; i--){
			if(up[a][i] != up[b][i]){
				a = up[a][i];
				b = up[b][i];
			}
		}
		return up[a][0];
	};

	
	
	auto go = [&](int a, int p, int type){
		int QQ = n+1;
		while(a != p){
			int idx = par_index[a];
			if(type == 1) edge1[idx] = 1;
			else edge2[idx] = 1;
			a = up[a][0];
		}
	};
	
	auto on_path=[&](int a, int p, int type){
		while(a != p){
		//	cout << a << ' ';
			int idx = par_index[a];
			if(type == a) return 1;  
			a = up[a][0];
		}
	//	cout << '\n';
		if(p == type) return 1;
		return 0;
	};
	
	for(int i = 0;i < q; i++){
		for(int k = 1; k < n; k++){
			edge1[k] = 0;
			edge2[k] = 0;
		}
		auto [a, b] = query[i];
		int lc = lca(a, b);
		for(int j = 0;j < q; j++){
			if(i == j) continue;
			auto [a1, b1] = query[j];
			int lc1 = lca(a1, b1);
			//a1, lc1 -> b
			//b1, lc1 -> a
			if(on_path(b1, lc1, a) && a != lc1){
			//cout << b1 << ' ' << lc1 << " = " << a << " -> ";
				cout << "No";
				return;
			}
			if(on_path(a1, lc1, b) && b != lc1){
			//	cout << a1 << " " << lc1 << " = " << b << " -> ";
				cout << "No";
				return;
			}
		
		}
	}
	
	for(int i = 0;i < q; i++){
		for(int j = 0; j < q; j++){
			if(i == j) continue;
			auto [a, b] = query[i];
			auto [a1, b1] = query[j];
			int lc = lca(a, b);
			int lc1 = lca(a1, b1);
			
			for(int k = 1; k < n; k++) edge1[k] = 0;
			
			go(a, lc, 1);
			go(b, lc, 1);
			int ok = 1;
			while(a1 != lc1){
				int idx = par_index[a1];
				if(!edge1[idx]){
					ok = 0;
					break;
				}
				a1 = up[a1][0];
			}
			while(b1 != lc1){
				int idx = par_index[b1];
				if(!edge1[idx]){
					ok = 0;
					break;
				}
				b1 = up[b1][0];
			}
			
			if(ok){
				cout << "No";
				return;
			}
			
			
		}
	}
	
	
	
	cout << "Yes";
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--){
		solve();
		cout << '\n';
	}
	
	return 0;
}

Compilation message (stderr)

jail.cpp: In lambda function:
jail.cpp:68:7: warning: unused variable 'QQ' [-Wunused-variable]
   68 |   int QQ = n+1;
      |       ^~
jail.cpp: In lambda function:
jail.cpp:80:8: warning: unused variable 'idx' [-Wunused-variable]
   80 |    int idx = par_index[a];
      |        ^~~
jail.cpp: In function 'void solve()':
jail.cpp:95:7: warning: unused variable 'lc' [-Wunused-variable]
   95 |   int lc = lca(a, b);
      |       ^~

• 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