oj.uz

Submission #692334

# Submission time Handle Problem Language Result Execution time Memory
692334 2023-02-01T10:59:29 Z flappybird Jail (JOI22_jail) C++17
49 / 100
 611 ms 527300 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 4001010
#define MAXS 20
#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 94 ms 188204 KB Output is correct
2 Correct 85 ms 188252 KB Output is correct
3 Correct 98 ms 188236 KB Output is correct
4 Correct 157 ms 188460 KB Output is correct
5 Correct 250 ms 188468 KB Output is correct
6 Correct 96 ms 188572 KB Output is correct
7 Correct 96 ms 188688 KB Output is correct
8 Correct 103 ms 188788 KB Output is correct
9 Correct 611 ms 198672 KB Output is correct
10 Runtime error 489 ms 527296 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 99 ms 188256 KB Output is correct
2 Correct 92 ms 188260 KB Output is correct
3 Correct 91 ms 188572 KB Output is correct
4 Correct 105 ms 188768 KB Output is correct
5 Correct 101 ms 188600 KB Output is correct
6 Correct 94 ms 188680 KB Output is correct
7 Correct 102 ms 188604 KB Output is correct
8 Correct 110 ms 188620 KB Output is correct
9 Correct 109 ms 188620 KB Output is correct
10 Correct 94 ms 188584 KB Output is correct
11 Correct 100 ms 188624 KB Output is correct
12 Correct 91 ms 188564 KB Output is correct
13 Correct 94 ms 188660 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 188256 KB Output is correct
2 Correct 92 ms 188260 KB Output is correct
3 Correct 91 ms 188572 KB Output is correct
4 Correct 105 ms 188768 KB Output is correct
5 Correct 101 ms 188600 KB Output is correct
6 Correct 94 ms 188680 KB Output is correct
7 Correct 102 ms 188604 KB Output is correct
8 Correct 110 ms 188620 KB Output is correct
9 Correct 109 ms 188620 KB Output is correct
10 Correct 94 ms 188584 KB Output is correct
11 Correct 100 ms 188624 KB Output is correct
12 Correct 91 ms 188564 KB Output is correct
13 Correct 94 ms 188660 KB Output is correct
14 Correct 94 ms 188160 KB Output is correct
15 Correct 95 ms 188260 KB Output is correct
16 Correct 111 ms 188688 KB Output is correct
17 Correct 110 ms 188688 KB Output is correct
18 Correct 105 ms 188668 KB Output is correct
19 Correct 95 ms 188184 KB Output is correct
20 Correct 97 ms 188620 KB Output is correct
21 Correct 104 ms 188632 KB Output is correct
22 Correct 107 ms 188812 KB Output is correct
23 Correct 93 ms 188188 KB Output is correct
24 Correct 90 ms 188356 KB Output is correct
25 Correct 102 ms 188748 KB Output is correct
26 Correct 89 ms 188564 KB Output is correct
27 Correct 95 ms 188640 KB Output is correct
28 Correct 88 ms 188176 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 188256 KB Output is correct
2 Correct 92 ms 188260 KB Output is correct
3 Correct 91 ms 188572 KB Output is correct
4 Correct 105 ms 188768 KB Output is correct
5 Correct 101 ms 188600 KB Output is correct
6 Correct 94 ms 188680 KB Output is correct
7 Correct 102 ms 188604 KB Output is correct
8 Correct 110 ms 188620 KB Output is correct
9 Correct 109 ms 188620 KB Output is correct
10 Correct 94 ms 188584 KB Output is correct
11 Correct 100 ms 188624 KB Output is correct
12 Correct 91 ms 188564 KB Output is correct
13 Correct 94 ms 188660 KB Output is correct
14 Correct 94 ms 188160 KB Output is correct
15 Correct 95 ms 188260 KB Output is correct
16 Correct 111 ms 188688 KB Output is correct
17 Correct 110 ms 188688 KB Output is correct
18 Correct 105 ms 188668 KB Output is correct
19 Correct 95 ms 188184 KB Output is correct
20 Correct 97 ms 188620 KB Output is correct
21 Correct 104 ms 188632 KB Output is correct
22 Correct 107 ms 188812 KB Output is correct
23 Correct 93 ms 188188 KB Output is correct
24 Correct 90 ms 188356 KB Output is correct
25 Correct 102 ms 188748 KB Output is correct
26 Correct 89 ms 188564 KB Output is correct
27 Correct 95 ms 188640 KB Output is correct
28 Correct 88 ms 188176 KB Output is correct
29 Correct 98 ms 188744 KB Output is correct
30 Correct 98 ms 188600 KB Output is correct
31 Correct 94 ms 188640 KB Output is correct
32 Correct 97 ms 188748 KB Output is correct
33 Correct 95 ms 188684 KB Output is correct
34 Correct 94 ms 188592 KB Output is correct
35 Correct 93 ms 188544 KB Output is correct
36 Correct 93 ms 188656 KB Output is correct
37 Correct 89 ms 188588 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 188256 KB Output is correct
2 Correct 92 ms 188260 KB Output is correct
3 Correct 91 ms 188572 KB Output is correct
4 Correct 105 ms 188768 KB Output is correct
5 Correct 101 ms 188600 KB Output is correct
6 Correct 94 ms 188680 KB Output is correct
7 Correct 102 ms 188604 KB Output is correct
8 Correct 110 ms 188620 KB Output is correct
9 Correct 109 ms 188620 KB Output is correct
10 Correct 94 ms 188584 KB Output is correct
11 Correct 100 ms 188624 KB Output is correct
12 Correct 91 ms 188564 KB Output is correct
13 Correct 94 ms 188660 KB Output is correct
14 Correct 94 ms 188160 KB Output is correct
15 Correct 95 ms 188260 KB Output is correct
16 Correct 111 ms 188688 KB Output is correct
17 Correct 110 ms 188688 KB Output is correct
18 Correct 105 ms 188668 KB Output is correct
19 Correct 95 ms 188184 KB Output is correct
20 Correct 97 ms 188620 KB Output is correct
21 Correct 104 ms 188632 KB Output is correct
22 Correct 107 ms 188812 KB Output is correct
23 Correct 93 ms 188188 KB Output is correct
24 Correct 90 ms 188356 KB Output is correct
25 Correct 102 ms 188748 KB Output is correct
26 Correct 89 ms 188564 KB Output is correct
27 Correct 95 ms 188640 KB Output is correct
28 Correct 88 ms 188176 KB Output is correct
29 Correct 98 ms 188744 KB Output is correct
30 Correct 98 ms 188600 KB Output is correct
31 Correct 94 ms 188640 KB Output is correct
32 Correct 97 ms 188748 KB Output is correct
33 Correct 95 ms 188684 KB Output is correct
34 Correct 94 ms 188592 KB Output is correct
35 Correct 93 ms 188544 KB Output is correct
36 Correct 93 ms 188656 KB Output is correct
37 Correct 89 ms 188588 KB Output is correct
38 Correct 597 ms 198776 KB Output is correct
39 Runtime error 408 ms 527300 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 84 ms 188224 KB Output is correct
2 Correct 89 ms 188364 KB Output is correct
3 Correct 84 ms 188260 KB Output is correct
4 Correct 87 ms 188184 KB Output is correct
5 Correct 122 ms 188308 KB Output is correct
6 Correct 91 ms 188644 KB Output is correct
7 Correct 90 ms 188600 KB Output is correct
8 Correct 89 ms 188272 KB Output is correct
9 Correct 96 ms 188184 KB Output is correct
10 Correct 93 ms 188384 KB Output is correct
11 Correct 86 ms 188236 KB Output is correct
12 Correct 90 ms 188588 KB Output is correct
13 Correct 171 ms 188488 KB Output is correct
14 Correct 260 ms 188612 KB Output is correct
15 Correct 206 ms 188448 KB Output is correct
16 Runtime error 433 ms 519956 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 94 ms 188204 KB Output is correct
2 Correct 85 ms 188252 KB Output is correct
3 Correct 98 ms 188236 KB Output is correct
4 Correct 157 ms 188460 KB Output is correct
5 Correct 250 ms 188468 KB Output is correct
6 Correct 96 ms 188572 KB Output is correct
7 Correct 96 ms 188688 KB Output is correct
8 Correct 103 ms 188788 KB Output is correct
9 Correct 611 ms 198672 KB Output is correct
10 Runtime error 489 ms 527296 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -