oj.uz

Submission #828776

# Submission time Handle Problem Language Result Execution time Memory
828776 2023-08-17T15:55:08 Z QwertyPi Inside information (BOI21_servers) C++14
50 / 100
 585 ms 56408 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1.2e5 + 11;
const int LGN = 17;
vector<pair<int, int>> G[MAXN];
int isq[MAXN * 2], ans[MAXN * 2];

void share(int a, int b, int t){
	G[a].push_back({b, t});
	G[b].push_back({a, t});
}

int p[MAXN], anc[LGN][MAXN];
bool _inc[LGN][MAXN], _dec[LGN][MAXN];
int _max[LGN][MAXN], _min[LGN][MAXN];
int c[MAXN], dep[MAXN];

void dfs(int v, int pa = -1){
	if(pa == -1){
		p[v] = anc[0][v] = v; for(int j = 1; j < LGN; j++) anc[j][v] = v;
	}
	for(auto [u, t] : G[v]){
		if(u != pa){
			p[u] = anc[0][u] = v; for(int j = 1; j < LGN; j++) anc[j][u] = anc[j - 1][anc[j - 1][u]]; 
			dep[u] = dep[v] + 1; _max[0][u] = _min[0][u] = t; _inc[0][u] = _dec[0][u] = true; c[u] = t;
			for(int j = 1; j < LGN; j++){
				_max[j][u] = max(_max[j - 1][u], _max[j - 1][anc[j - 1][u]]);
				_min[j][u] = min(_min[j - 1][u], _min[j - 1][anc[j - 1][u]]);
				_inc[j][u] = _inc[j - 1][u] && _inc[j - 1][anc[j - 1][u]] && _max[j - 1][u] <= _min[j - 1][anc[j - 1][u]];
				_dec[j][u] = _dec[j - 1][u] && _dec[j - 1][anc[j - 1][u]] && _min[j - 1][u] >= _max[j - 1][anc[j - 1][u]];
			}
			dfs(u, v);
		}
	}
}
int kth_anc(int u, int k){
	for(int j = LGN - 1; j >= 0; j--){
		if(k & (1 << j)) u = anc[j][u];
	}
	return u;
}
int lca(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	u = kth_anc(u, dep[u] - dep[v]);
	for(int j = LGN - 1; j >= 0; j--){
		if(anc[j][u] != anc[j][v])
			u = anc[j][u], v = anc[j][v];
	}
	return u == v ? u : p[u];
}

bool is_inc(int u, int l){
	int diff = dep[u] - dep[l];
	int d = __lg(diff);
	return _inc[d][u] && _inc[d][kth_anc(u, diff - (1 << d))];
}

bool is_dec(int u, int l){
	int diff = dep[u] - dep[l];
	int d = __lg(diff);
	return _dec[d][u] && _dec[d][kth_anc(u, diff - (1 << d))];
}

struct query_1{
	int a, d, t;
};

struct query_2{
	int d, t;
};

vector<query_1> Q1;
vector<query_2> Q2;

void query(int a, int d, int t){
	Q1.push_back({a, d, t});
}

void count(int d, int t){
	Q2.push_back({d, t});
}

int32_t main(){
	int n, k; cin >> n >> k;
	for(int t = 0; t < n + k - 1; t++){
		char c; cin >> c;
		if(c == 'S'){
			int a, b; cin >> a >> b;
			share(a, b, t);
		}else if(c == 'Q'){
			int a, d; cin >> a >> d;
			query(a, d, t);
			isq[t] = 1;
		}else{
			int d; cin >> d;
			count(d, t);
			isq[t] = 2;
		}
	}

	dfs(1);
	for(auto [a, d, t] : Q1){
		if(a == d){
			ans[t] = true;
			continue;
		}
		int l = lca(a, d);
		ans[t] = true;
		if(l == a){
			ans[t] = is_inc(d, l);
			ans[t] &= c[kth_anc(d, dep[d] - dep[a] - 1)] <= t;
		}else if(l == d){
			ans[t] = is_dec(a, l);
			ans[t] &= c[a] <= t;
		}else{
			ans[t] = is_inc(d, l);
			ans[t] &= is_dec(a, l);
			ans[t] &= c[kth_anc(a, dep[a] - dep[l] - 1)] >= c[kth_anc(d, dep[d] - dep[l] - 1)];
			ans[t] &= c[a] <= t;
		}
	}

	for(int t = 0; t < n + k - 1; t++){
		if(isq[t] == 1){
			cout << (ans[t] ? "yes" : "no") << endl;
		}else if(isq[t] == 2){
			cout << ans[t] << endl;
		}
	}
}

Compilation message

servers.cpp: In function 'void dfs(int, int)':
servers.cpp:24:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |  for(auto [u, t] : G[v]){
      |           ^
servers.cpp: In function 'int32_t main()':
servers.cpp:104:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |  for(auto [a, d, t] : Q1){
      |           ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 168 ms 6304 KB Output is correct
2 Correct 209 ms 8760 KB Output is correct
3 Correct 197 ms 8920 KB Output is correct
4 Correct 199 ms 8964 KB Output is correct
5 Correct 190 ms 9280 KB Output is correct
6 Correct 198 ms 8820 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 168 ms 6304 KB Output is correct
2 Correct 209 ms 8760 KB Output is correct
3 Correct 197 ms 8920 KB Output is correct
4 Correct 199 ms 8964 KB Output is correct
5 Correct 190 ms 9280 KB Output is correct
6 Correct 198 ms 8820 KB Output is correct
7 Incorrect 181 ms 7048 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 179 ms 6372 KB Output is correct
2 Correct 454 ms 43712 KB Output is correct
3 Correct 412 ms 43716 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 179 ms 6372 KB Output is correct
2 Correct 454 ms 43712 KB Output is correct
3 Correct 412 ms 43716 KB Output is correct
4 Incorrect 168 ms 7176 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 158 ms 6328 KB Output is correct
2 Correct 329 ms 56408 KB Output is correct
3 Correct 334 ms 56388 KB Output is correct
4 Correct 353 ms 56236 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 6328 KB Output is correct
2 Correct 329 ms 56408 KB Output is correct
3 Correct 334 ms 56388 KB Output is correct
4 Correct 353 ms 56236 KB Output is correct
5 Incorrect 185 ms 7184 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 176 ms 6264 KB Output is correct
2 Correct 349 ms 44116 KB Output is correct
3 Correct 328 ms 44172 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 6264 KB Output is correct
2 Correct 349 ms 44116 KB Output is correct
3 Correct 328 ms 44172 KB Output is correct
4 Incorrect 187 ms 7120 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 165 ms 6264 KB Output is correct
2 Correct 331 ms 56368 KB Output is correct
3 Correct 358 ms 56312 KB Output is correct
4 Correct 356 ms 56308 KB Output is correct
5 Correct 163 ms 7184 KB Output is correct
6 Correct 348 ms 44100 KB Output is correct
7 Correct 328 ms 44156 KB Output is correct
8 Correct 465 ms 44968 KB Output is correct
9 Correct 411 ms 44968 KB Output is correct
10 Correct 474 ms 50880 KB Output is correct
11 Correct 585 ms 49880 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 165 ms 6264 KB Output is correct
2 Correct 331 ms 56368 KB Output is correct
3 Correct 358 ms 56312 KB Output is correct
4 Correct 356 ms 56308 KB Output is correct
5 Correct 163 ms 7184 KB Output is correct
6 Correct 348 ms 44100 KB Output is correct
7 Correct 328 ms 44156 KB Output is correct
8 Correct 465 ms 44968 KB Output is correct
9 Correct 411 ms 44968 KB Output is correct
10 Correct 474 ms 50880 KB Output is correct
11 Correct 585 ms 49880 KB Output is correct
12 Incorrect 164 ms 7060 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 188 ms 6344 KB Output is correct
2 Correct 190 ms 8728 KB Output is correct
3 Correct 193 ms 8960 KB Output is correct
4 Correct 224 ms 8916 KB Output is correct
5 Correct 188 ms 9252 KB Output is correct
6 Correct 196 ms 8784 KB Output is correct
7 Correct 163 ms 7244 KB Output is correct
8 Correct 436 ms 43680 KB Output is correct
9 Correct 395 ms 43624 KB Output is correct
10 Correct 163 ms 7188 KB Output is correct
11 Correct 332 ms 56324 KB Output is correct
12 Correct 342 ms 56352 KB Output is correct
13 Correct 332 ms 56288 KB Output is correct
14 Correct 162 ms 7176 KB Output is correct
15 Correct 350 ms 44056 KB Output is correct
16 Correct 337 ms 44164 KB Output is correct
17 Correct 439 ms 45044 KB Output is correct
18 Correct 441 ms 44952 KB Output is correct
19 Correct 435 ms 50848 KB Output is correct
20 Correct 471 ms 49912 KB Output is correct
21 Correct 417 ms 44228 KB Output is correct
22 Correct 414 ms 44328 KB Output is correct
23 Correct 411 ms 44488 KB Output is correct
24 Correct 418 ms 44748 KB Output is correct
25 Correct 438 ms 47348 KB Output is correct
26 Correct 407 ms 43284 KB Output is correct
27 Correct 387 ms 43244 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 188 ms 6344 KB Output is correct
2 Correct 190 ms 8728 KB Output is correct
3 Correct 193 ms 8960 KB Output is correct
4 Correct 224 ms 8916 KB Output is correct
5 Correct 188 ms 9252 KB Output is correct
6 Correct 196 ms 8784 KB Output is correct
7 Correct 163 ms 7244 KB Output is correct
8 Correct 436 ms 43680 KB Output is correct
9 Correct 395 ms 43624 KB Output is correct
10 Correct 163 ms 7188 KB Output is correct
11 Correct 332 ms 56324 KB Output is correct
12 Correct 342 ms 56352 KB Output is correct
13 Correct 332 ms 56288 KB Output is correct
14 Correct 162 ms 7176 KB Output is correct
15 Correct 350 ms 44056 KB Output is correct
16 Correct 337 ms 44164 KB Output is correct
17 Correct 439 ms 45044 KB Output is correct
18 Correct 441 ms 44952 KB Output is correct
19 Correct 435 ms 50848 KB Output is correct
20 Correct 471 ms 49912 KB Output is correct
21 Correct 417 ms 44228 KB Output is correct
22 Correct 414 ms 44328 KB Output is correct
23 Correct 411 ms 44488 KB Output is correct
24 Correct 418 ms 44748 KB Output is correct
25 Correct 438 ms 47348 KB Output is correct
26 Correct 407 ms 43284 KB Output is correct
27 Correct 387 ms 43244 KB Output is correct
28 Incorrect 165 ms 7124 KB Extra information in the output file
29 Halted 0 ms 0 KB -