oj.uz

Submission #999360

# Submission time Handle Problem Language Result Execution time Memory
999360 2024-06-15T10:58:54 Z TAhmed33 Inside information (BOI21_servers) C++
50 / 100
 173 ms 113232 KB 
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 3e5 + 25;
    const int B = 18;
    int n, q;
    array <int, 4> queries[MAXN];
    vector <pair <int, int>> adj[MAXN];
    int p[MAXN], dp[B][MAXN], dep[MAXN], top[B][MAXN], inc[B][MAXN], decr[B][MAXN];
    void dfs (int pos, int par) {
    	p[pos] = par;
    	for (auto [j, k] : adj[pos]) {
    		if (j == par) continue;
    		dep[j] = 1 + dep[pos];
    		dp[0][j] = pos;
    		top[0][j] = k;
    		inc[0][j] = 1;
    		decr[0][j] = 1;
    		for (int i = 1; i < B; i++) {
    			dp[i][j] = dp[i - 1][dp[i - 1][j]];
    			top[i][j] = top[i - 1][dp[i - 1][j]];
    			inc[i][j] = inc[i - 1][j] && inc[i - 1][dp[i - 1][j]] && (top[i - 1][j] < top[0][dp[i - 1][j]]);
    			decr[i][j] = decr[i - 1][j] && decr[i - 1][dp[i - 1][j]] && (top[i - 1][j] > top[0][dp[i - 1][j]]);
    		} 
    		dfs(j, pos);
    	}
    }
    int jump (int a, int b) {
    	for (int i = B - 1; i >= 0; i--) {
    		if (b & (1 << i)) {
    			a = dp[i][a];
    		}
    	}
    	return a;
    }
    int lca (int a, int b) {
    	if (dep[a] > dep[b]) swap(a, b);
    	b = jump(b, dep[b] - dep[a]);
    	if (a == b) return a;
    	for (int i = B - 1; i >= 0; i--) {
    		int x = dp[i][a], y = dp[i][b];
    		if (x && y && x != y) {
    			a = x, b = y;
    		}
    	}
    	return dp[0][a];
    }
    pair <bool, int> check_inc (int a, int b, int x) {
    	bool f = 1; int last = 0;
    	for (int i = B - 1; i >= 0; i--) {
    		int z = dp[i][a];
    		if (!z || dep[z] <= dep[b]) continue;
    		f &= inc[i][a]; f &= top[0][a] > last;
    		last = top[i][a]; a = z;
    	}
    	f &= top[0][a] <= x;
    	f &= top[0][a] > last;
    	return {f, top[0][a]};
    } 
    pair <bool, int> check_decr (int a, int b, int x) {
    	bool f = top[0][a] <= x; int last = 1e9;
    	for (int i = B - 1; i >= 0; i--) {
    		int z = dp[i][a];
    		if (!z || dep[z] <= dep[b]) continue;
    		f &= decr[i][a]; f &= top[0][a] < last;
    		last = top[i][a]; a = z;
    	}
    	f &= top[0][a] < last;
    	return {f, top[0][a]};
    }
    bool check (int a, int b, int x) {
    	if (a == b) return 1;
    	int z = lca(a, b);
    	if (z == a) return check_decr(b, z, x).first;
    	if (z == b) return check_inc(a, z, x).first;
    	auto g = check_inc(a, z, x), h = check_decr(b, z, x);
    	return g.first && h.first && g.second < h.second;
    }
    void solve () {
    	cin >> n >> q;
    	int ee = 0;
    	for (int i = 1; i <= n - 1 + q; i++) {
    		char c; cin >> c;
    		if (c == 'S') {	
    			int x, y; cin >> x >> y;
    			adj[x].push_back({y, i});
    			adj[y].push_back({x, i});
    		} else if (c == 'Q') {
    			int x, y; cin >> x >> y;
    			queries[++ee] = {1, y, x, i};
    		} else {
    			int x; cin >> x;
    			queries[++ee] = {2, x, 0, i};
    		}
    	}
    	dfs(1, 0);
    	for (int i = 1; i <= q; i++) {
    		auto g = check(queries[i][1], queries[i][2], queries[i][3]);
    		cout << (g ? "yes\n" : "no\n");
    	}
    }		
    signed main () {
    	ios::sync_with_stdio(0); cin.tie(0);
    	int tc = 1; //cin >> tc;
    	while (tc--) solve();
    }

Compilation message

servers.cpp: In function 'void dfs(int, int)':
servers.cpp:11:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   11 |      for (auto [j, k] : adj[pos]) {
      |                ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 95060 KB Output is correct
2 Correct 42 ms 95316 KB Output is correct
3 Correct 38 ms 95312 KB Output is correct
4 Correct 61 ms 95312 KB Output is correct
5 Correct 55 ms 95580 KB Output is correct
6 Correct 35 ms 95316 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 95060 KB Output is correct
2 Correct 42 ms 95316 KB Output is correct
3 Correct 38 ms 95312 KB Output is correct
4 Correct 61 ms 95312 KB Output is correct
5 Correct 55 ms 95580 KB Output is correct
6 Correct 35 ms 95316 KB Output is correct
7 Incorrect 30 ms 95060 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 95068 KB Output is correct
2 Correct 89 ms 100884 KB Output is correct
3 Correct 94 ms 100804 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 95068 KB Output is correct
2 Correct 89 ms 100884 KB Output is correct
3 Correct 94 ms 100804 KB Output is correct
4 Incorrect 29 ms 95060 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 95056 KB Output is correct
2 Correct 118 ms 112980 KB Output is correct
3 Correct 96 ms 113044 KB Output is correct
4 Correct 114 ms 112976 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 95056 KB Output is correct
2 Correct 118 ms 112980 KB Output is correct
3 Correct 96 ms 113044 KB Output is correct
4 Correct 114 ms 112976 KB Output is correct
5 Incorrect 25 ms 95056 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 95056 KB Output is correct
2 Correct 82 ms 100924 KB Output is correct
3 Correct 85 ms 101264 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 95056 KB Output is correct
2 Correct 82 ms 100924 KB Output is correct
3 Correct 85 ms 101264 KB Output is correct
4 Incorrect 29 ms 95040 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 95052 KB Output is correct
2 Correct 99 ms 112976 KB Output is correct
3 Correct 100 ms 112980 KB Output is correct
4 Correct 125 ms 113132 KB Output is correct
5 Correct 30 ms 95056 KB Output is correct
6 Correct 88 ms 100948 KB Output is correct
7 Correct 89 ms 101460 KB Output is correct
8 Correct 148 ms 101624 KB Output is correct
9 Correct 128 ms 101728 KB Output is correct
10 Correct 128 ms 107676 KB Output is correct
11 Correct 170 ms 106600 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 95052 KB Output is correct
2 Correct 99 ms 112976 KB Output is correct
3 Correct 100 ms 112980 KB Output is correct
4 Correct 125 ms 113132 KB Output is correct
5 Correct 30 ms 95056 KB Output is correct
6 Correct 88 ms 100948 KB Output is correct
7 Correct 89 ms 101460 KB Output is correct
8 Correct 148 ms 101624 KB Output is correct
9 Correct 128 ms 101728 KB Output is correct
10 Correct 128 ms 107676 KB Output is correct
11 Correct 170 ms 106600 KB Output is correct
12 Incorrect 27 ms 95056 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 95060 KB Output is correct
2 Correct 42 ms 95312 KB Output is correct
3 Correct 36 ms 95312 KB Output is correct
4 Correct 64 ms 95312 KB Output is correct
5 Correct 53 ms 95572 KB Output is correct
6 Correct 45 ms 95340 KB Output is correct
7 Correct 31 ms 95060 KB Output is correct
8 Correct 98 ms 100800 KB Output is correct
9 Correct 97 ms 100836 KB Output is correct
10 Correct 24 ms 95016 KB Output is correct
11 Correct 106 ms 113232 KB Output is correct
12 Correct 97 ms 113068 KB Output is correct
13 Correct 119 ms 112980 KB Output is correct
14 Correct 30 ms 95312 KB Output is correct
15 Correct 90 ms 101176 KB Output is correct
16 Correct 89 ms 101464 KB Output is correct
17 Correct 153 ms 101716 KB Output is correct
18 Correct 125 ms 101716 KB Output is correct
19 Correct 134 ms 107600 KB Output is correct
20 Correct 173 ms 106576 KB Output is correct
21 Correct 99 ms 100928 KB Output is correct
22 Correct 113 ms 101044 KB Output is correct
23 Correct 106 ms 101460 KB Output is correct
24 Correct 113 ms 101280 KB Output is correct
25 Correct 140 ms 104032 KB Output is correct
26 Correct 109 ms 100696 KB Output is correct
27 Correct 118 ms 100680 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 95060 KB Output is correct
2 Correct 42 ms 95312 KB Output is correct
3 Correct 36 ms 95312 KB Output is correct
4 Correct 64 ms 95312 KB Output is correct
5 Correct 53 ms 95572 KB Output is correct
6 Correct 45 ms 95340 KB Output is correct
7 Correct 31 ms 95060 KB Output is correct
8 Correct 98 ms 100800 KB Output is correct
9 Correct 97 ms 100836 KB Output is correct
10 Correct 24 ms 95016 KB Output is correct
11 Correct 106 ms 113232 KB Output is correct
12 Correct 97 ms 113068 KB Output is correct
13 Correct 119 ms 112980 KB Output is correct
14 Correct 30 ms 95312 KB Output is correct
15 Correct 90 ms 101176 KB Output is correct
16 Correct 89 ms 101464 KB Output is correct
17 Correct 153 ms 101716 KB Output is correct
18 Correct 125 ms 101716 KB Output is correct
19 Correct 134 ms 107600 KB Output is correct
20 Correct 173 ms 106576 KB Output is correct
21 Correct 99 ms 100928 KB Output is correct
22 Correct 113 ms 101044 KB Output is correct
23 Correct 106 ms 101460 KB Output is correct
24 Correct 113 ms 101280 KB Output is correct
25 Correct 140 ms 104032 KB Output is correct
26 Correct 109 ms 100696 KB Output is correct
27 Correct 118 ms 100680 KB Output is correct
28 Incorrect 32 ms 95064 KB Extra information in the output file
29 Halted 0 ms 0 KB -