oj.uz

Submission #709111

# Submission time Handle Problem Language Result Execution time Memory
709111 2023-03-13T06:28:36 Z minhcool Jail (JOI22_jail) C++17
0 / 100
 10 ms 14448 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;

int n, m;

vector<int> Adj[N];
vector<int> Adj2[N];// all nodes j that go after i

int deg[N];

void init(){
	for(int i = 1; i <= max(n, m); i++){
		Adj[i].clear();
		Adj2[i].clear();
		deg[i] = 0;
	}
}

int anc[N][20], d[N];

void dfs(int u, int p){
	for(auto v : Adj[u]){
		if(v == p) continue;
		d[v] = d[u] + 1;
		anc[v][0] = u;
		for(int i = 1; i <= 19; i++) anc[v][i] = anc[anc[v][i - 1]][i - 1];
		dfs(v, u);
	}
}

int lca(int x, int y){
	if(d[x] > d[y]) swap(x, y);
	for(int i = 19; i >= 0; i--) if((d[y] - d[x]) >= (1LL << i)) y = anc[y][i];
	if(x == y) return x;
	for(int i = 19; i >= 0; i--){
		if(anc[x][i] != anc[y][i]){
			x = anc[x][i], y = anc[y][i];
		}
	}
	return anc[x][0];
}

int dist(int x, int y){
	return d[x] + d[y] - 2 * d[lca(x, y)];
}

bool in(int a, int b, int c){
	return (dist(a, c) + dist(b, c) == dist(a, b));
}

int st[N], en[N];

void process(){
    cin >> n;
    init();
    for(int i = 1; i < n; i++){
    	int x, y;
    	cin >> x >> y;
    	Adj[x].pb(y);
    	Adj[y].pb(x);
	}
	cin >> m;
	dfs(1, 1);
	for(int i = 1; i <= m; i++) cin >> st[i] >> en[i];
	for(int i = 1; i <= m; i++){
		for(int j = i + 1; j <= m; j++){
			bool ck1 = in(st[i], en[i], st[j]);
			bool ck2 = in(st[i], en[i], en[j]);
			bool ck3 = in(st[j], en[j], st[i]);
			bool ck4 = in(st[j], en[j], en[i]);
			//cout << ck1 << " " << ck2 << " " << ck3 << " " << ck4 << "\n";
			bool temp1 = (ck1 & ck4), temp2 = (ck2 & ck3);
			if(temp1 & temp2){
				cout << "No\n";
				return;
			}
			if(temp1){
				Adj2[i].pb(j);
				deg[j]++;
			}
			if(temp2){
				Adj2[j].pb(i);
				deg[i]++;
			}
		}
	}
	queue<int> q;
	for(int i = 1; i <= m; i++) if(!deg[i]) q.push(i);
	int cnt = 0;
	while(!q.empty()){
		cnt++;
		int u = q.front();
		//cout << u << "\n";
		q.pop();
		for(auto v : Adj2[u]){
			deg[v]--;
			if(!deg[v]) q.push(v);
		}
	}
	if(cnt == m) cout << "Yes\n";
	else cout << "No\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    //freopen("KEK.inp", "r", stdin);
    //freopen("KEK.out", "w", stdout);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) process();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 10 ms 14420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Incorrect 9 ms 14432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Incorrect 9 ms 14432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Incorrect 9 ms 14432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Incorrect 9 ms 14432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 10 ms 14420 KB Output isn't correct
3 Halted 0 ms 0 KB -