oj.uz

Submission #709423

# Submission time Handle Problem Language Result Execution time Memory
709423 2023-03-13T14:26:48 Z minhcool Jail (JOI22_jail) C++17
0 / 100
 5000 ms 54832 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];
 
int anc[N][20], d[N]; 

int le[N], ri[N];
 
void init(){
	for(int i = 1; i <= max(n, m); i++){
		Adj[i].clear();
		Adj2[i].clear();
		deg[i] = 0;
		for(int j = 0; j < 19; j++) anc[i][j] = 0;
		d[i] = 0;		
	}
}

int cnt;
 
void dfs(int u, int p){
	cnt++;
	le[u] = cnt;
	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);
	}
	ri[u] = cnt;
}
 
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 mn = min(le[a], le[b]), mx = max(le[a], le[b]);
	if(mn <= le[c] && mx >= le[c] && mx <= ri[c]) return 1;
	if(mn >= le[c] && mn <= ri[c] && mx > ri[c]) return 1;
	return 0;
}
 
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++){
			assert(st[i] != st[j]);
			assert(en[i] != en[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[j].pb(i);
				deg[i]++;
			}
			if(temp2){
				Adj2[i].pb(j);
				deg[j]++;
			}
		}
	}
	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 7 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 9 ms 14416 KB Output is correct
4 Correct 24 ms 14820 KB Output is correct
5 Correct 39 ms 15104 KB Output is correct
6 Correct 9 ms 14492 KB Output is correct
7 Correct 12 ms 14548 KB Output is correct
8 Correct 11 ms 14564 KB Output is correct
9 Correct 58 ms 18620 KB Output is correct
10 Correct 67 ms 50964 KB Output is correct
11 Correct 17 ms 14568 KB Output is correct
12 Correct 38 ms 15444 KB Output is correct
13 Execution timed out 5103 ms 54832 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14452 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 10 ms 14420 KB Output is correct
5 Correct 14 ms 14548 KB Output is correct
6 Incorrect 8 ms 14420 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 9 ms 14416 KB Output is correct
4 Correct 24 ms 14820 KB Output is correct
5 Correct 39 ms 15104 KB Output is correct
6 Correct 9 ms 14492 KB Output is correct
7 Correct 12 ms 14548 KB Output is correct
8 Correct 11 ms 14564 KB Output is correct
9 Correct 58 ms 18620 KB Output is correct
10 Correct 67 ms 50964 KB Output is correct
11 Correct 17 ms 14568 KB Output is correct
12 Correct 38 ms 15444 KB Output is correct
13 Execution timed out 5103 ms 54832 KB Time limit exceeded
14 Halted 0 ms 0 KB -