oj.uz

Submission #733651

# Submission time Handle Problem Language Result Execution time Memory
733651 2023-05-01T06:50:45 Z QwertyPi Jail (JOI22_jail) C++14
0 / 100
 26 ms 6396 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N_MAX = 1.2e5 + 11; 
const int LG_N = 20;
vector<int> G[N_MAX], H[N_MAX];
vector<pair<int, int>> Q;
int anc[LG_N][N_MAX], p[N_MAX], d[N_MAX];
int owner[N_MAX];
bool vis[N_MAX];
bool in_stack[N_MAX];

int n, q;
void clear(){
	for(int i = 0; i <= n; i++) G[i].clear();
	for(int i = 0; i <= n; i++) H[i].clear();
	fill(owner, owner + n + 1, 0);
	fill(vis, vis + n + 1, 0);
	fill(in_stack, in_stack + n + 1, 0);
	Q.clear();
}

void dfs(int v, int pa = -1){
	for(auto i : G[v]){
		if(i != pa){
			p[i] = anc[0][i] = v; d[i] = d[v] + 1; 
			for(int j = 1; j < LG_N; j++){
				anc[j][i] = anc[j - 1][anc[j - 1][i]];
			}
			dfs(i, v);
		}
	}
}

bool dfs2(int v){
	vis[v] = in_stack[v] = true;
	for(auto i : H[v]){
		if(in_stack[i]) return true;
		if(vis[i]) continue;
		bool fail = dfs2(i);
		if(fail) return true;
	}
	in_stack[v] = false;
	return false;
}

int kth_anc(int u, int k){
	for(int j = LG_N - 1; j >= 0; j--){
		if(k & (1 << j)) u = anc[j][u];
	}
	return u;
}

int lca(int u, int v){
	if(d[u] < d[v]) swap(u, v);
	u = kth_anc(u, d[u] - d[v]);
	for(int j = LG_N - 1; j >= 0; j--){
		if(anc[j][u] != anc[j][v]){
			u = anc[j][u], v = anc[j][v];
		}
	}
	return u == v ? u : p[u];
}

void solve(){
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1);
	cin >> q;
	Q.push_back({-1, -1});
	for(int i = 1; i <= q; i++){
		int x, y; cin >> x >> y;
		Q.push_back({x, y});
		owner[x] = i;
	}
	for(int i = 1; i <= q; i++){
		auto [x, y] = Q[i]; int l = lca(x, y);
		vector<int> P, p1, p2;
		while(x != l){
			p1.push_back(x); x = p[x];
		}
		while(y != l){
			p2.push_back(y); y = p[y];
		}
		for(auto i : p1) P.push_back(i);
		P.push_back(l);
		reverse(p2.begin(), p2.end());
		for(auto i : p2) P.push_back(i);
		for(auto p : P) {
			if(owner[p] && owner[p] != i){
				H[i].push_back(owner[p]);
			}
		}
	}
	bool fail = false;
	for(int i = 1; i <= q; i++){
		if(!vis[i]) fail |= dfs2(i);
		if(fail) break;
	}
	cout << (!fail ? "Yes" : "No") << endl;
}

int32_t main(){
	int q; cin >> q;
	while(q--){
		solve();
		clear();
	}
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:83:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |   auto [x, y] = Q[i]; int l = lca(x, y);
      |        ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 4 ms 5948 KB Output is correct
3 Incorrect 5 ms 6084 KB Output isn't correct
4 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 4 ms 5948 KB Output is correct
3 Incorrect 5 ms 6084 KB Output isn't correct
4 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 4 ms 5948 KB Output is correct
3 Incorrect 5 ms 6084 KB Output isn't correct
4 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 4 ms 5948 KB Output is correct
3 Incorrect 5 ms 6084 KB Output isn't correct
4 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 4 ms 5944 KB Output is correct
3 Correct 4 ms 5948 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Incorrect 19 ms 6224 KB Output isn't correct
6 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 4 ms 5948 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Incorrect 26 ms 6396 KB Output isn't correct
5 Halted 0 ms 0 KB -