oj.uz

Submission #814765

# Submission time Handle Problem Language Result Execution time Memory
814765 2023-08-08T09:42:33 Z WonderfulWhale Jail (JOI22_jail) C++17
5 / 100
 225 ms 12108 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

vector<int> G[120009];
vector<int> G2[120009];
int tin[120009], tout[120009], T;
int jp2[120009][20];
int deg[120009];
pii tab[120009];

void dfs(int x, int y) {
	tin[x] = ++T;
	jp2[x][0] = y;
	for(int i=1;i<20;i++) jp2[x][i] = jp2[jp2[x][i-1]][i-1];
	for(int z:G[x]) if(z!=y) dfs(z, x);
	tout[x] = ++T;
}

bool is_ancestor(int x, int y) {
	return tin[x]<=tin[y]&&tout[x]>=tout[y];
}

int lca(int x, int y) {
	if(is_ancestor(x, y)) return x;
	if(is_ancestor(y, x)) return y;
	for(int i=19;i>=0;i--) {
		if(!is_ancestor(jp2[x][i], y)) {
			x = jp2[x][i];
		}
	}
	return jp2[x][0];
}

bool is_on_path(int x, int a, int b) {
	return is_ancestor(a, x)&&is_ancestor(x, b);
}

bool f(int x, int a, int b) {
	int y = lca(a, b);
	//cerr << "lca: " << a << " " << b << " " << y << "\n";
	//cerr << "checking: " << x << " " << a << " " << b << " " << (is_on_path(x, y, a)||is_on_path(x, y, b)) << "\n";
	return is_on_path(x, y, a)||is_on_path(x, y, b);
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int q=1;
	cin >> q;
	while(q--) {
		int n, m;
		cin >> n;
		for(int i=1;i<=n;i++) G[i].clear();
		for(int i=0;i<n-1;i++) {
			int a, b;
			cin >> a >> b;
			G[a].pb(b);
			G[b].pb(a);
		}
		tin[0] = T = 0;
		dfs(1, 0);
		tout[0] = T;
		cin >> m;
		for(int i=0;i<m;i++) {
			G2[i].clear();
			deg[i] = 0;
		}
		for(int i=0;i<m;i++) {
			cin >> tab[i].st >> tab[i].nd;
		}
		int edge_cnt = 0;
		for(int i=0;i<m;i++) {
			for(int j=0;j<m;j++) {
				if(i==j) continue;
				if(f(tab[j].st, tab[i].st, tab[i].nd)) {
					//cerr << "adding: " << i << " " << j << "\n";
					G2[i].pb(j);
					deg[j]++;
					edge_cnt++;
				} 
				if(f(tab[j].nd, tab[i].st, tab[i].nd)) {
					//cerr << "adding: " << j <<  " " << i << "\n";
					G2[j].pb(i);
					deg[i]++;
					edge_cnt++;
				}
			}
		}
		int cnt = 0;
		queue<int> Q;
		for(int i=0;i<m;i++) {
			if(deg[i]==0) {
				Q.push(i);
			}
		}
		while(sz(Q)) {
			cnt++;
			int x = Q.front();
			Q.pop();
			for(int y:G2[x]) {
				deg[y]--;
				if(deg[y]==0) Q.push(y);
			}
		}
		if(cnt==m) {
			assert(edge_cnt<5*m);
			cout << "Yes\n";
		} else {
			cout << "No\n";
		}
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 4 ms 5972 KB Output is correct
4 Correct 14 ms 6024 KB Output is correct
5 Correct 26 ms 6004 KB Output is correct
6 Correct 4 ms 5972 KB Output is correct
7 Runtime error 11 ms 11996 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 3 ms 5972 KB Output is correct
6 Correct 3 ms 5972 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 3 ms 5972 KB Output is correct
10 Correct 3 ms 5972 KB Output is correct
11 Correct 3 ms 5972 KB Output is correct
12 Correct 4 ms 5972 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 3 ms 5972 KB Output is correct
6 Correct 3 ms 5972 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 3 ms 5972 KB Output is correct
10 Correct 3 ms 5972 KB Output is correct
11 Correct 3 ms 5972 KB Output is correct
12 Correct 4 ms 5972 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct
14 Correct 2 ms 5972 KB Output is correct
15 Correct 4 ms 5972 KB Output is correct
16 Runtime error 11 ms 12088 KB Execution killed with signal 6
17 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 3 ms 5972 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 3 ms 5972 KB Output is correct
6 Correct 3 ms 5972 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 3 ms 5972 KB Output is correct
10 Correct 3 ms 5972 KB Output is correct
11 Correct 3 ms 5972 KB Output is correct
12 Correct 4 ms 5972 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct
14 Correct 2 ms 5972 KB Output is correct
15 Correct 4 ms 5972 KB Output is correct
16 Runtime error 11 ms 12088 KB Execution killed with signal 6
17 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 3 ms 5972 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 3 ms 5972 KB Output is correct
6 Correct 3 ms 5972 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 3 ms 5972 KB Output is correct
10 Correct 3 ms 5972 KB Output is correct
11 Correct 3 ms 5972 KB Output is correct
12 Correct 4 ms 5972 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct
14 Correct 2 ms 5972 KB Output is correct
15 Correct 4 ms 5972 KB Output is correct
16 Runtime error 11 ms 12088 KB Execution killed with signal 6
17 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 5972 KB Output is correct
3 Correct 2 ms 5972 KB Output is correct
4 Correct 2 ms 5972 KB Output is correct
5 Correct 9 ms 5976 KB Output is correct
6 Correct 3 ms 5972 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 3 ms 5972 KB Output is correct
10 Correct 3 ms 5972 KB Output is correct
11 Correct 4 ms 5972 KB Output is correct
12 Correct 23 ms 6052 KB Output is correct
13 Correct 225 ms 6260 KB Output is correct
14 Correct 134 ms 6020 KB Output is correct
15 Runtime error 87 ms 12108 KB Execution killed with signal 6
16 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 3 ms 5972 KB Output is correct
3 Correct 4 ms 5972 KB Output is correct
4 Correct 14 ms 6024 KB Output is correct
5 Correct 26 ms 6004 KB Output is correct
6 Correct 4 ms 5972 KB Output is correct
7 Runtime error 11 ms 11996 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -