oj.uz

Submission #692331

# Submission time Handle Problem Language Result Execution time Memory
692331 2023-02-01T10:58:21 Z flappybird Jail (JOI22_jail) C++17
49 / 100
 541 ms 481172 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 2501010
#define MAXS 18
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int N, M, K;
int sp[MAX][MAXS];
int getind(int x, int t, int istd) {
	return x * MAXS * 2 + t * 2 + istd;
}
vector<int> tree[MAX], adj[MAX];
int dep[MAX];
int S[MAX];
int T[MAX];
int deg[MAX];
int vis[MAX];
void dfs(int x) {
	int i;
	for (i = 1; i < MAXS; i++) if (~sp[x][i - 1]) sp[x][i] = sp[sp[x][i - 1]][i - 1];
	for (auto v : tree[x]) if (v != sp[x][0]) {
		sp[v][0] = x;
		dep[v] = dep[x] + 1;
		dfs(v);
	}
}
int lca(int u, int v) {
	int i;
	if (dep[u] != dep[v]) {
		if (dep[u] > dep[v]) swap(u, v);
		int d = dep[v] - dep[u];
		for (i = 0; i < MAXS; i++) if (d >> i & 1) v = sp[v][i];
	}
	if (u == v) return u;
	for (i = MAXS - 1; i >= 0; i--) if (sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
	return sp[u][0];
}
void solve() {
	cin >> N;
	int i, j;
	for (i = 0; i < N; i++) for (j = 0; j < MAXS; j++) sp[i][j] = -1;
	for (i = 0; i < N; i++) tree[i].clear();
	int a, b;
	for (i = 0; i < N - 1; i++) {
		cin >> a >> b; a--; b--;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	cin >> M;
	for (i = 0; i < M; i++) cin >> S[i] >> T[i], S[i]--, T[i]--;
	dep[0] = 1;
	dfs(0);
	int sind = getind(N - 1, MAXS - 1, 1) + 1;
	int K = sind + M;
	for (i = 0; i < K; i++) adj[i].clear(), vis[i] = 0, deg[i] = 0;
	for (j = 1; j < MAXS; j++) {
		for (i = 0; i < N; i++) {
			adj[getind(i, j - 1, 0)].push_back(getind(i, j, 0));
			adj[getind(i, j, 1)].push_back(getind(i, j - 1, 1));
			if (~sp[i][j - 1]) adj[getind(sp[i][j - 1], j - 1, 0)].push_back(getind(i, j, 0));
			if (~sp[i][j - 1]) adj[getind(i, j, 1)].push_back(getind(sp[i][j - 1], j - 1, 1));
		}
	}
	for (i = 0; i < M; i++) {
		adj[getind(T[i], 0, 1)].push_back(i + sind);
		adj[i + sind].push_back(getind(S[i], 0, 0));
		int l = lca(S[i], T[i]);
		if (l == S[i] || l == T[i]) {
			int v = S[i] + T[i] - l;
			v = sp[v][0];
			int d = dep[v];
			if (~l) d -= dep[l];
			for (j = MAXS - 1; j >= 0; j--) if (d >> j & 1) {
				adj[getind(v, j, 0)].push_back(i + sind);
				adj[i + sind].push_back(getind(v, j, 1));
				v = sp[v][j];
			}
		}
		else {
			l = sp[l][0];
			for (auto v : { sp[S[i]][0], sp[T[i]][0] }) {
				int d = dep[v];
				if (~l) d -= dep[l];
				for (j = MAXS - 1; j >= 0; j--) if (d >> j & 1) {
					adj[getind(v, j, 0)].push_back(i + sind);
					adj[i + sind].push_back(getind(v, j, 1));
					v = sp[v][j];
				}
			}
		}
		adj[i + sind].push_back(getind(S[i], 0, 1));
		adj[getind(T[i], 0, 0)].push_back(i + sind);
	}
	queue<int> q;
	for (i = 0; i < K; i++) for (auto v : adj[i]) deg[v]++;
	for (i = 0; i < K; i++) if (!deg[i]) q.push(i);
	while (q.size()) {
		int t = q.front();
		q.pop();
		if (vis[t]) continue;
		vis[t] = 1;
		for (auto v : adj[t]) {
			if (!vis[v]) {
				deg[v]--;
				if (!deg[v]) q.push(v);
			}
		}
	}
	for (i = sind; i < sind + M; i++) if (!vis[i]) {
		cout << "No" << ln;
		return;
	}
	cout << "Yes" << ln;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int Q;
	cin >> Q;
	while (Q--) solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 117780 KB Output is correct
2 Correct 60 ms 117832 KB Output is correct
3 Correct 53 ms 117784 KB Output is correct
4 Correct 118 ms 118256 KB Output is correct
5 Correct 195 ms 118752 KB Output is correct
6 Correct 63 ms 118236 KB Output is correct
7 Correct 61 ms 118220 KB Output is correct
8 Correct 62 ms 118184 KB Output is correct
9 Correct 515 ms 128428 KB Output is correct
10 Runtime error 480 ms 481172 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117756 KB Output is correct
2 Correct 60 ms 117792 KB Output is correct
3 Correct 61 ms 118176 KB Output is correct
4 Correct 62 ms 118220 KB Output is correct
5 Correct 64 ms 118168 KB Output is correct
6 Correct 61 ms 118132 KB Output is correct
7 Correct 67 ms 118248 KB Output is correct
8 Correct 68 ms 118244 KB Output is correct
9 Correct 61 ms 118224 KB Output is correct
10 Correct 61 ms 118244 KB Output is correct
11 Correct 62 ms 118240 KB Output is correct
12 Correct 59 ms 118092 KB Output is correct
13 Correct 61 ms 118168 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117756 KB Output is correct
2 Correct 60 ms 117792 KB Output is correct
3 Correct 61 ms 118176 KB Output is correct
4 Correct 62 ms 118220 KB Output is correct
5 Correct 64 ms 118168 KB Output is correct
6 Correct 61 ms 118132 KB Output is correct
7 Correct 67 ms 118248 KB Output is correct
8 Correct 68 ms 118244 KB Output is correct
9 Correct 61 ms 118224 KB Output is correct
10 Correct 61 ms 118244 KB Output is correct
11 Correct 62 ms 118240 KB Output is correct
12 Correct 59 ms 118092 KB Output is correct
13 Correct 61 ms 118168 KB Output is correct
14 Correct 53 ms 117776 KB Output is correct
15 Correct 55 ms 117900 KB Output is correct
16 Correct 61 ms 118208 KB Output is correct
17 Correct 60 ms 118180 KB Output is correct
18 Correct 69 ms 118148 KB Output is correct
19 Correct 53 ms 117772 KB Output is correct
20 Correct 61 ms 118220 KB Output is correct
21 Correct 63 ms 118152 KB Output is correct
22 Correct 66 ms 118260 KB Output is correct
23 Correct 66 ms 117876 KB Output is correct
24 Correct 53 ms 117980 KB Output is correct
25 Correct 65 ms 118180 KB Output is correct
26 Correct 54 ms 118188 KB Output is correct
27 Correct 65 ms 118232 KB Output is correct
28 Correct 67 ms 117836 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117756 KB Output is correct
2 Correct 60 ms 117792 KB Output is correct
3 Correct 61 ms 118176 KB Output is correct
4 Correct 62 ms 118220 KB Output is correct
5 Correct 64 ms 118168 KB Output is correct
6 Correct 61 ms 118132 KB Output is correct
7 Correct 67 ms 118248 KB Output is correct
8 Correct 68 ms 118244 KB Output is correct
9 Correct 61 ms 118224 KB Output is correct
10 Correct 61 ms 118244 KB Output is correct
11 Correct 62 ms 118240 KB Output is correct
12 Correct 59 ms 118092 KB Output is correct
13 Correct 61 ms 118168 KB Output is correct
14 Correct 53 ms 117776 KB Output is correct
15 Correct 55 ms 117900 KB Output is correct
16 Correct 61 ms 118208 KB Output is correct
17 Correct 60 ms 118180 KB Output is correct
18 Correct 69 ms 118148 KB Output is correct
19 Correct 53 ms 117772 KB Output is correct
20 Correct 61 ms 118220 KB Output is correct
21 Correct 63 ms 118152 KB Output is correct
22 Correct 66 ms 118260 KB Output is correct
23 Correct 66 ms 117876 KB Output is correct
24 Correct 53 ms 117980 KB Output is correct
25 Correct 65 ms 118180 KB Output is correct
26 Correct 54 ms 118188 KB Output is correct
27 Correct 65 ms 118232 KB Output is correct
28 Correct 67 ms 117836 KB Output is correct
29 Correct 60 ms 118264 KB Output is correct
30 Correct 61 ms 118260 KB Output is correct
31 Correct 61 ms 118180 KB Output is correct
32 Correct 61 ms 118220 KB Output is correct
33 Correct 67 ms 118360 KB Output is correct
34 Correct 65 ms 118180 KB Output is correct
35 Correct 67 ms 118128 KB Output is correct
36 Correct 65 ms 118196 KB Output is correct
37 Correct 69 ms 118140 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117756 KB Output is correct
2 Correct 60 ms 117792 KB Output is correct
3 Correct 61 ms 118176 KB Output is correct
4 Correct 62 ms 118220 KB Output is correct
5 Correct 64 ms 118168 KB Output is correct
6 Correct 61 ms 118132 KB Output is correct
7 Correct 67 ms 118248 KB Output is correct
8 Correct 68 ms 118244 KB Output is correct
9 Correct 61 ms 118224 KB Output is correct
10 Correct 61 ms 118244 KB Output is correct
11 Correct 62 ms 118240 KB Output is correct
12 Correct 59 ms 118092 KB Output is correct
13 Correct 61 ms 118168 KB Output is correct
14 Correct 53 ms 117776 KB Output is correct
15 Correct 55 ms 117900 KB Output is correct
16 Correct 61 ms 118208 KB Output is correct
17 Correct 60 ms 118180 KB Output is correct
18 Correct 69 ms 118148 KB Output is correct
19 Correct 53 ms 117772 KB Output is correct
20 Correct 61 ms 118220 KB Output is correct
21 Correct 63 ms 118152 KB Output is correct
22 Correct 66 ms 118260 KB Output is correct
23 Correct 66 ms 117876 KB Output is correct
24 Correct 53 ms 117980 KB Output is correct
25 Correct 65 ms 118180 KB Output is correct
26 Correct 54 ms 118188 KB Output is correct
27 Correct 65 ms 118232 KB Output is correct
28 Correct 67 ms 117836 KB Output is correct
29 Correct 60 ms 118264 KB Output is correct
30 Correct 61 ms 118260 KB Output is correct
31 Correct 61 ms 118180 KB Output is correct
32 Correct 61 ms 118220 KB Output is correct
33 Correct 67 ms 118360 KB Output is correct
34 Correct 65 ms 118180 KB Output is correct
35 Correct 67 ms 118128 KB Output is correct
36 Correct 65 ms 118196 KB Output is correct
37 Correct 69 ms 118140 KB Output is correct
38 Correct 541 ms 128532 KB Output is correct
39 Runtime error 459 ms 481068 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 117784 KB Output is correct
2 Correct 56 ms 117716 KB Output is correct
3 Correct 57 ms 117724 KB Output is correct
4 Correct 54 ms 117724 KB Output is correct
5 Correct 80 ms 117964 KB Output is correct
6 Correct 64 ms 118124 KB Output is correct
7 Correct 66 ms 118184 KB Output is correct
8 Correct 54 ms 117836 KB Output is correct
9 Correct 58 ms 117760 KB Output is correct
10 Correct 56 ms 117892 KB Output is correct
11 Correct 63 ms 117836 KB Output is correct
12 Correct 61 ms 118172 KB Output is correct
13 Correct 133 ms 118652 KB Output is correct
14 Correct 218 ms 118824 KB Output is correct
15 Correct 168 ms 118660 KB Output is correct
16 Runtime error 452 ms 466124 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 117780 KB Output is correct
2 Correct 60 ms 117832 KB Output is correct
3 Correct 53 ms 117784 KB Output is correct
4 Correct 118 ms 118256 KB Output is correct
5 Correct 195 ms 118752 KB Output is correct
6 Correct 63 ms 118236 KB Output is correct
7 Correct 61 ms 118220 KB Output is correct
8 Correct 62 ms 118184 KB Output is correct
9 Correct 515 ms 128428 KB Output is correct
10 Runtime error 480 ms 481172 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -