oj.uz

Submission #574236

# Submission time Handle Problem Language Result Execution time Memory
574236 2022-06-08T08:29:22 Z amunduzbaev Inside information (BOI21_servers) C++17
100 / 100
 626 ms 60880 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 3e5 + 5;
vector<ar<int, 2>> edges[N];
int par[N][20], ed[N], lift[N][20];
int tin[N], tout[N], t, d[N];

void dfs(int u){
	tin[u] = ++t;
	lift[u][0] = (ed[u] > ed[par[u][0]]);
	for(int j=1;j<20;j++){
		par[u][j] = par[par[u][j-1]][j-1];
		lift[u][j] = lift[u][j-1] + lift[par[u][j-1]][j-1];
	}
	
	for(auto x : edges[u]){
		if(x[0] == par[u][0]) continue;
		par[x[0]][0] = u, ed[x[0]] = x[1];
		d[x[0]] = d[u] + 1;
		dfs(x[0]);
	}
	tout[u] = t;
}

bool is(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

int check(int a, int b, int t){
	if(a == b) return true;
	//~ cout<<a<<" "<<b<<" "<<is(a, b)<<" "<<is(b, a)<<"\n";
	if(is(a, b)){
		int tot = 0;
		for(int j=19;~j;j--){
			if(!is(par[b][j], a)){
				tot += lift[b][j];
				b = par[b][j];
			}
		}
		return (!tot && ed[b] <= t);
	}
	
	if(is(b, a)){
		swap(a, b);
		int tot = 0, o = b;
		for(int j=19;~j;j--){
			if(!is(par[b][j], a)){
				tot += lift[b][j];
				b = par[b][j];
			}
		}
		//~ cout<<tot<<" "<<d[o] - d[b]<<" "<<ed[o]<<"\n";
		return (tot == d[o] - d[b] && ed[o] <= t);
	}
	
	int t1 = 0, t2 = 0, o = a;
	for(int j=19;~j;j--){
		if(!is(par[b][j], a)){
			t1 += lift[b][j];
			b = par[b][j];
		}
		
		if(!is(par[a][j], b)){
			t2 += lift[a][j];
			a = par[a][j];
		}
	}
	//~ cout<<a<<" "<<b<<"\n";
	//~ cout<<t1<<" "<<t2<<" "<<d[a] - d[o]<<" "<<ed[a]<<" "<<ed[b]<<" "<<ed[o]<<"\n";
	return (t1 == 0 && t2 == d[o] - d[a] && ed[a] > ed[b] && ed[o] <= t);
}

struct BIT{
	int tree[N];
	void add(int i, int v){
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){
		int r = 0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
	
	int get(int l, int r){
		return get(r) - get(l - 1);
	}
}tree;

int res[N], used[N], sub[N];
int to[N], ver[N], pos[N];
vector<int> qq[N], tt, tot;
int face[N];

void dfs1(int u, int p = -1){
	sub[u] = 1;
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		pos[x[1]] = x[0];
		to[x[0]] = x[1], dfs1(x[0], u);
		sub[u] += sub[x[0]];
	}
}

int cen(int u, int n, int p = -1){
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		if(sub[x[0]] * 2 > n) return cen(x[0], n, u);
	} return u;
}

void dfs2(int u, int inc = 1, int dec = 1, int p = -1){
	if(dec){
		for(auto x : qq[u]){
			if(x < to[face[u]]) continue;
			tt.push_back(x);
			res[x]++;
		}
	}
	if(inc){
		tot.push_back(to[u]);
	}
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		face[x[0]] = face[u];
		dfs2(x[0], inc & (to[u] < x[1]), dec & (to[u] > x[1]), u);
	}
}

void dec(int u){
	dfs1(u);
	u = cen(u, sub[u]);
	dfs1(u);
	
	tt.clear(), tot.clear();
	for(auto x : edges[u]){
		if(used[x[0]]) continue;
		face[x[0]] = x[0];
		dfs2(x[0], 1, 1, u);
	}
	
	sort(tt.begin(), tt.end());
	sort(tot.begin(), tot.end());
	
	for(auto x : qq[u]){
		int cc = upper_bound(tot.begin(), tot.end(), x) - tot.begin();
		res[x] += cc;
	}
	
	int j = 0;
	for(auto x : tt){ 
		while(j < (int)tot.size() && tot[j] < x){
			tree.add(to[face[pos[tot[j]]]], 1);
			j++;
		}
		
		res[x] += tree.get(to[face[ver[x]]] + 1, N - 1);
	}
	
	for(int l=0;l<j;l++) tree.add(to[face[pos[tot[l]]]], -1);
	used[u] = 1;
	for(auto x : edges[u]){
		if(used[x[0]]) continue;
		dec(x[0]);
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<ar<int, 3>> q;
	for(int i=1;i<n + m;i++){
		char c; cin>>c;
		if(c == 'S'){
			int a, b; cin>>a>>b;
			edges[a].push_back({b, i});
			edges[b].push_back({a, i});
		} if(c == 'Q') {
			int a, b; cin>>a>>b;
			q.push_back({a, b, i});
		} if(c == 'C'){
			cin>>ver[i];
			qq[ver[i]].push_back(i);
			q.push_back({-1, ver[i], i});
		}
	}
	
	par[1][0] = 1;
	dfs(1);
	dec(1);
	
	for(auto [a, b, t] : q){
		if(~a){
			if(check(a, b, t)) cout<<"yes\n";
			else cout<<"no\n";
		} else { 
			cout<<++res[t]<<"\n";
		}
	}
}

/*

6 3
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5

5 1
S 5 4
S 4 1
S 1 2
S 2 3
Q 3 5

*/

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 16496 KB Output is correct
2 Correct 46 ms 17584 KB Output is correct
3 Correct 43 ms 17708 KB Output is correct
4 Correct 62 ms 17672 KB Output is correct
5 Correct 60 ms 17532 KB Output is correct
6 Correct 48 ms 17316 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 16496 KB Output is correct
2 Correct 46 ms 17584 KB Output is correct
3 Correct 43 ms 17708 KB Output is correct
4 Correct 62 ms 17672 KB Output is correct
5 Correct 60 ms 17532 KB Output is correct
6 Correct 48 ms 17316 KB Output is correct
7 Correct 36 ms 17452 KB Output is correct
8 Correct 49 ms 20660 KB Output is correct
9 Correct 45 ms 20732 KB Output is correct
10 Correct 59 ms 20672 KB Output is correct
11 Correct 66 ms 20000 KB Output is correct
12 Correct 44 ms 20384 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16544 KB Output is correct
2 Correct 143 ms 45480 KB Output is correct
3 Correct 136 ms 45488 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16544 KB Output is correct
2 Correct 143 ms 45480 KB Output is correct
3 Correct 136 ms 45488 KB Output is correct
4 Correct 37 ms 17480 KB Output is correct
5 Correct 203 ms 48456 KB Output is correct
6 Correct 129 ms 48052 KB Output is correct
7 Correct 133 ms 48920 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16592 KB Output is correct
2 Correct 332 ms 52892 KB Output is correct
3 Correct 323 ms 52884 KB Output is correct
4 Correct 228 ms 53432 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16592 KB Output is correct
2 Correct 332 ms 52892 KB Output is correct
3 Correct 323 ms 52884 KB Output is correct
4 Correct 228 ms 53432 KB Output is correct
5 Correct 35 ms 17356 KB Output is correct
6 Correct 367 ms 60024 KB Output is correct
7 Correct 299 ms 60880 KB Output is correct
8 Correct 396 ms 60536 KB Output is correct
9 Correct 417 ms 60548 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16584 KB Output is correct
2 Correct 191 ms 44616 KB Output is correct
3 Correct 288 ms 44948 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16584 KB Output is correct
2 Correct 191 ms 44616 KB Output is correct
3 Correct 288 ms 44948 KB Output is correct
4 Correct 34 ms 17356 KB Output is correct
5 Correct 275 ms 51808 KB Output is correct
6 Correct 283 ms 51364 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16576 KB Output is correct
2 Correct 383 ms 52936 KB Output is correct
3 Correct 310 ms 52908 KB Output is correct
4 Correct 274 ms 53460 KB Output is correct
5 Correct 34 ms 16496 KB Output is correct
6 Correct 182 ms 44708 KB Output is correct
7 Correct 269 ms 44860 KB Output is correct
8 Correct 320 ms 44928 KB Output is correct
9 Correct 328 ms 45352 KB Output is correct
10 Correct 335 ms 49968 KB Output is correct
11 Correct 347 ms 48932 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16576 KB Output is correct
2 Correct 383 ms 52936 KB Output is correct
3 Correct 310 ms 52908 KB Output is correct
4 Correct 274 ms 53460 KB Output is correct
5 Correct 34 ms 16496 KB Output is correct
6 Correct 182 ms 44708 KB Output is correct
7 Correct 269 ms 44860 KB Output is correct
8 Correct 320 ms 44928 KB Output is correct
9 Correct 328 ms 45352 KB Output is correct
10 Correct 335 ms 49968 KB Output is correct
11 Correct 347 ms 48932 KB Output is correct
12 Correct 40 ms 17344 KB Output is correct
13 Correct 384 ms 60216 KB Output is correct
14 Correct 280 ms 60764 KB Output is correct
15 Correct 413 ms 60512 KB Output is correct
16 Correct 371 ms 60484 KB Output is correct
17 Correct 37 ms 18240 KB Output is correct
18 Correct 281 ms 51804 KB Output is correct
19 Correct 286 ms 51200 KB Output is correct
20 Correct 381 ms 51496 KB Output is correct
21 Correct 363 ms 52544 KB Output is correct
22 Correct 452 ms 56036 KB Output is correct
23 Correct 626 ms 55332 KB Output is correct
24 Correct 482 ms 54328 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16576 KB Output is correct
2 Correct 48 ms 17524 KB Output is correct
3 Correct 42 ms 17732 KB Output is correct
4 Correct 55 ms 17748 KB Output is correct
5 Correct 55 ms 17584 KB Output is correct
6 Correct 51 ms 17372 KB Output is correct
7 Correct 40 ms 16600 KB Output is correct
8 Correct 142 ms 45564 KB Output is correct
9 Correct 140 ms 45436 KB Output is correct
10 Correct 33 ms 16588 KB Output is correct
11 Correct 312 ms 52936 KB Output is correct
12 Correct 330 ms 52860 KB Output is correct
13 Correct 226 ms 53408 KB Output is correct
14 Correct 33 ms 16576 KB Output is correct
15 Correct 227 ms 44700 KB Output is correct
16 Correct 242 ms 44924 KB Output is correct
17 Correct 306 ms 44812 KB Output is correct
18 Correct 391 ms 45348 KB Output is correct
19 Correct 346 ms 49916 KB Output is correct
20 Correct 447 ms 48940 KB Output is correct
21 Correct 155 ms 45352 KB Output is correct
22 Correct 165 ms 44988 KB Output is correct
23 Correct 250 ms 44900 KB Output is correct
24 Correct 221 ms 44968 KB Output is correct
25 Correct 451 ms 50156 KB Output is correct
26 Correct 293 ms 44248 KB Output is correct
27 Correct 341 ms 44452 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16576 KB Output is correct
2 Correct 48 ms 17524 KB Output is correct
3 Correct 42 ms 17732 KB Output is correct
4 Correct 55 ms 17748 KB Output is correct
5 Correct 55 ms 17584 KB Output is correct
6 Correct 51 ms 17372 KB Output is correct
7 Correct 40 ms 16600 KB Output is correct
8 Correct 142 ms 45564 KB Output is correct
9 Correct 140 ms 45436 KB Output is correct
10 Correct 33 ms 16588 KB Output is correct
11 Correct 312 ms 52936 KB Output is correct
12 Correct 330 ms 52860 KB Output is correct
13 Correct 226 ms 53408 KB Output is correct
14 Correct 33 ms 16576 KB Output is correct
15 Correct 227 ms 44700 KB Output is correct
16 Correct 242 ms 44924 KB Output is correct
17 Correct 306 ms 44812 KB Output is correct
18 Correct 391 ms 45348 KB Output is correct
19 Correct 346 ms 49916 KB Output is correct
20 Correct 447 ms 48940 KB Output is correct
21 Correct 155 ms 45352 KB Output is correct
22 Correct 165 ms 44988 KB Output is correct
23 Correct 250 ms 44900 KB Output is correct
24 Correct 221 ms 44968 KB Output is correct
25 Correct 451 ms 50156 KB Output is correct
26 Correct 293 ms 44248 KB Output is correct
27 Correct 341 ms 44452 KB Output is correct
28 Correct 36 ms 17388 KB Output is correct
29 Correct 49 ms 20568 KB Output is correct
30 Correct 50 ms 20712 KB Output is correct
31 Correct 57 ms 20620 KB Output is correct
32 Correct 52 ms 19948 KB Output is correct
33 Correct 48 ms 20476 KB Output is correct
34 Correct 35 ms 18264 KB Output is correct
35 Correct 170 ms 51140 KB Output is correct
36 Correct 135 ms 49760 KB Output is correct
37 Correct 130 ms 50800 KB Output is correct
38 Correct 41 ms 18280 KB Output is correct
39 Correct 377 ms 60140 KB Output is correct
40 Correct 291 ms 60864 KB Output is correct
41 Correct 414 ms 60520 KB Output is correct
42 Correct 463 ms 60576 KB Output is correct
43 Correct 39 ms 18244 KB Output is correct
44 Correct 253 ms 51772 KB Output is correct
45 Correct 294 ms 51268 KB Output is correct
46 Correct 353 ms 51620 KB Output is correct
47 Correct 331 ms 52512 KB Output is correct
48 Correct 416 ms 55884 KB Output is correct
49 Correct 579 ms 55440 KB Output is correct
50 Correct 577 ms 54324 KB Output is correct
51 Correct 151 ms 52112 KB Output is correct
52 Correct 198 ms 51896 KB Output is correct
53 Correct 137 ms 51308 KB Output is correct
54 Correct 138 ms 50860 KB Output is correct
55 Correct 183 ms 51140 KB Output is correct
56 Correct 226 ms 51148 KB Output is correct
57 Correct 389 ms 55612 KB Output is correct
58 Correct 447 ms 51572 KB Output is correct
59 Correct 338 ms 49908 KB Output is correct