oj.uz

Submission #890984

# Submission time Handle Problem Language Result Execution time Memory
890984 2023-12-22T05:48:32 Z iskhakkutbilim Jail (JOI22_jail) C++17
0 / 100
 5000 ms 1988 KB 
#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){
			QQ--;
			if(QQ == 0){
				assert(false);
			}
			int idx = par_index[a];
			if(type == 1) edge1[idx] = 1;
			else edge2[idx] = 1;
			a = up[a][0];
		}
	};
	
	
	for(auto [a, b] : query){
		int lc = lca(a, b);
		go(a, lc, 1);
		go(b, lc, 2);
	}
	
	for(int i = 1;i < n; i++){
		if(edge1[i] && edge2[i]){
			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;
			int QQ = n+1;
			while(a1 != lc1){
				QQ--;
				if(QQ == 0){
					assert(false);
				}
				int idx = par_index[a1];
				if(!edge1[idx]){
					ok = 0;
					break;
				}
				a1 = up[a1][0];
			}
			QQ = n+1;
			while(b1 != lc1){
				QQ--;
				if(QQ == 0){
					assert(false);
				}
				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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 13 ms 488 KB Output is correct
5 Correct 29 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 16 ms 348 KB Output is correct
9 Execution timed out 5048 ms 1988 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 13 ms 488 KB Output is correct
5 Correct 29 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 16 ms 348 KB Output is correct
9 Execution timed out 5048 ms 1988 KB Time limit exceeded
10 Halted 0 ms 0 KB -