oj.uz

Submission #528944

# Submission time Handle Problem Language Result Execution time Memory
528944 2022-02-21T19:33:20 Z Arnch Inside information (BOI21_servers) C++17
100 / 100
 708 ms 107896 KB 
// oooo
/*
 be hengam shena mesle y dasto pa cholofti ~
 bepa to masire dahane koose neyofti ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

// fen[0] -> soodi
// fen[1] -> nozoli 

struct node {
	int up, down;
	bool f;
	node() {
		up = down = f = 0;
	}
};
int n, k, t, r, hide[N], sz[N], h[N], u[N], v[N], ans[N], fen[N];
node cnt[N];
char type[N];
vector<int> con[N], his, A, B; vector<pair<int, int> > G[N], query[N];

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	return p1.second > p2.second;
}
void get_input() {
	cin >>n >>k;
	for(int i = 1; i < n + k; i++) {
		cin >>type[i];
		if(type[i] != 'C') {
			cin >>u[i] >>v[i], u[i]--, v[i]--;
			if(type[i] == 'S') 
				G[u[i]].push_back({v[i], i}), G[v[i]].push_back({u[i], i});
			else
				query[u[i]].push_back({v[i], i});
			continue;
		}	
		cin >>u[i], u[i]--;
		con[u[i]].push_back(i);
	}
	for(int i = 0; i < n; i++) 
		sort(All(G[i]), cmp);
}

void upd(int ind, int val) {
	for(++ind; ind < N; ind += ind & -ind) {
		fen[ind] += val;
		his.push_back(ind);
	}
}
int get(int ind) {
	int sum = 0;
	for(++ind; ind; ind -= ind & -ind) {
		sum += fen[ind];
	}
	return sum;
}

void plant(int x, int p = -1) {
	sz[x] = 1;
	for(auto &i : G[x]) {
		if(i.first == p || hide[i.first]) continue;
		plant(i.first, x);
		sz[x] += sz[i.first];
	}
}
int get_centroid(int x, int _n, int p = -1) {
	for(auto &i : G[x]) {
		if(i.first == p || hide[i.first]) continue;
		if(2 * sz[i.first] > _n) return get_centroid(i.first, _n, x);
	}
	return x;
}
void DFS0(int x, int p = -1) {
	for(auto &i : G[x]) {
		if(i.first == p || hide[i.first]) continue;
		if(i.second <= cnt[x].down && cnt[x].down <= cnt[x].up && cnt[x].f == 1) {
			cnt[i.first].f = 1;
			cnt[i.first].down = i.second;
			if(p == -1) cnt[i.first].up = i.second;
			else cnt[i.first].up = cnt[x].up;
		}
		else if(i.second >= cnt[x].down && cnt[x].down >= cnt[x].up && cnt[x].f == 1) {
			cnt[i.first].f = 1;
			cnt[i.first].down = i.second;
			if(p == -1) cnt[i.first].up = i.second;
			else cnt[i.first].up = cnt[x].up;
		}
		else {
			cnt[i.first].f = 0;
		}
		DFS0(i.first, x);
	}
	if(x != r) B.push_back(x);
}
void DFS1(int x, int p = -1) {
	if(x != r && cnt[x].f == 1) {
		for(auto &i : query[x]) {
			if(cnt[i.first].f == 0 || hide[i.first]) continue;
			if(i.first == r) {
				if(cnt[x].up <= cnt[x].down && i.second >= cnt[x].down) {
					ans[i.second] = 1;
				}
				continue;
			}
			if(cnt[i.first].up >= cnt[i.first].down && cnt[i.first].up <= cnt[x].up && cnt[x].up <= cnt[x].down && i.second >= cnt[x].down) {
				ans[i.second] = 1;
			}
		}
	}
	for(auto &i : G[x]) {
		if(hide[i.first] || i.first == p) continue;
		DFS1(i.first, x);
	}
	for(auto &i : con[x]) {
		if(cnt[x].f == 1 && cnt[x].up >= cnt[x].down && cnt[x].up <= i) {
			ans[i]++;
		}
	}
}
void DFS2(int x, int p = -1) {
	if(x != r && cnt[x].f == 1 && cnt[x].up >= cnt[x].down) {
		for(auto &i : con[x]) {
			ans[i] += get(i);
		}
	}
	if(x != r) A.push_back(x);
	for(auto &i : G[x]) {
		if(i.first == p || hide[i.first]) continue;
		DFS2(i.first, x);
	}
}
void solve(int x) {
	h[x] = 0, cnt[x].f = 1, DFS0(x);
	DFS1(x);
	for(auto &i : query[x]) {
		if(cnt[i.first].f == 0 || hide[i.first]) continue;
		if(cnt[i.first].up >= cnt[i.first].down && i.second >= cnt[i.first].up) {
			ans[i.second] = 1;
		}
	}	
	for(auto &i : G[x]) {
		if(hide[i.first]) continue;
		DFS2(i.first, x);
		for(auto &j : A) {
			if(cnt[j].f == 1 && cnt[j].up <= cnt[j].down) upd(cnt[j].down, 1);
		}
		A.clear();
	}
	for(auto &i : con[x]) {
		ans[i] += get(i);
	}

	for(auto &i : his) fen[i] = 0;
	his.clear();
	for(auto &i : B) cnt[i].up = cnt[i].down = cnt[i].f = 0;
	B.clear();
}
void decompose(int x) {
	plant(x);
	r = get_centroid(x, sz[x]);
	solve(r), hide[r] = 1;
	for(auto &i : G[r]) {
		if(hide[i.first]) continue;
		decompose(i.first);
	}
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);
	
	get_input();

	decompose(0);

	for(int i = 1; i < n + k; i++) {
		if(type[i] == 'S') continue;
		if(type[i] == 'Q') {
			(ans[i] == 1) ? (cout<<"yes\n") : (cout<<"no\n");
		}
		else {
			cout<<ans[i] <<'\n';
		}
	}

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 87036 KB Output is correct
2 Correct 72 ms 86864 KB Output is correct
3 Correct 78 ms 87064 KB Output is correct
4 Correct 77 ms 86984 KB Output is correct
5 Correct 71 ms 86736 KB Output is correct
6 Correct 68 ms 87068 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 87036 KB Output is correct
2 Correct 72 ms 86864 KB Output is correct
3 Correct 78 ms 87064 KB Output is correct
4 Correct 77 ms 86984 KB Output is correct
5 Correct 71 ms 86736 KB Output is correct
6 Correct 68 ms 87068 KB Output is correct
7 Correct 61 ms 86480 KB Output is correct
8 Correct 78 ms 86852 KB Output is correct
9 Correct 74 ms 86784 KB Output is correct
10 Correct 98 ms 86852 KB Output is correct
11 Correct 93 ms 86500 KB Output is correct
12 Correct 73 ms 86808 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 87040 KB Output is correct
2 Correct 203 ms 104008 KB Output is correct
3 Correct 197 ms 104056 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 87040 KB Output is correct
2 Correct 203 ms 104008 KB Output is correct
3 Correct 197 ms 104056 KB Output is correct
4 Correct 60 ms 86472 KB Output is correct
5 Correct 230 ms 103924 KB Output is correct
6 Correct 171 ms 102332 KB Output is correct
7 Correct 155 ms 102400 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 87132 KB Output is correct
2 Correct 481 ms 100488 KB Output is correct
3 Correct 440 ms 100484 KB Output is correct
4 Correct 340 ms 102936 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 87132 KB Output is correct
2 Correct 481 ms 100488 KB Output is correct
3 Correct 440 ms 100484 KB Output is correct
4 Correct 340 ms 102936 KB Output is correct
5 Correct 58 ms 86468 KB Output is correct
6 Correct 481 ms 102800 KB Output is correct
7 Correct 376 ms 103600 KB Output is correct
8 Correct 512 ms 100524 KB Output is correct
9 Correct 459 ms 100920 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 87024 KB Output is correct
2 Correct 385 ms 99152 KB Output is correct
3 Correct 365 ms 96508 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 87024 KB Output is correct
2 Correct 385 ms 99152 KB Output is correct
3 Correct 365 ms 96508 KB Output is correct
4 Correct 60 ms 86380 KB Output is correct
5 Correct 371 ms 101876 KB Output is correct
6 Correct 383 ms 99436 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 86980 KB Output is correct
2 Correct 471 ms 100496 KB Output is correct
3 Correct 461 ms 100496 KB Output is correct
4 Correct 363 ms 102896 KB Output is correct
5 Correct 58 ms 86612 KB Output is correct
6 Correct 331 ms 99148 KB Output is correct
7 Correct 356 ms 96472 KB Output is correct
8 Correct 384 ms 96636 KB Output is correct
9 Correct 441 ms 97344 KB Output is correct
10 Correct 564 ms 100800 KB Output is correct
11 Correct 539 ms 99992 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 86980 KB Output is correct
2 Correct 471 ms 100496 KB Output is correct
3 Correct 461 ms 100496 KB Output is correct
4 Correct 363 ms 102896 KB Output is correct
5 Correct 58 ms 86612 KB Output is correct
6 Correct 331 ms 99148 KB Output is correct
7 Correct 356 ms 96472 KB Output is correct
8 Correct 384 ms 96636 KB Output is correct
9 Correct 441 ms 97344 KB Output is correct
10 Correct 564 ms 100800 KB Output is correct
11 Correct 539 ms 99992 KB Output is correct
12 Correct 62 ms 86724 KB Output is correct
13 Correct 472 ms 101632 KB Output is correct
14 Correct 372 ms 103036 KB Output is correct
15 Correct 487 ms 102784 KB Output is correct
16 Correct 480 ms 102696 KB Output is correct
17 Correct 58 ms 87024 KB Output is correct
18 Correct 372 ms 102324 KB Output is correct
19 Correct 367 ms 99260 KB Output is correct
20 Correct 398 ms 100168 KB Output is correct
21 Correct 520 ms 100628 KB Output is correct
22 Correct 604 ms 103152 KB Output is correct
23 Correct 708 ms 103908 KB Output is correct
24 Correct 626 ms 103500 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 87136 KB Output is correct
2 Correct 72 ms 86900 KB Output is correct
3 Correct 69 ms 88136 KB Output is correct
4 Correct 79 ms 88144 KB Output is correct
5 Correct 74 ms 87756 KB Output is correct
6 Correct 69 ms 88216 KB Output is correct
7 Correct 60 ms 87336 KB Output is correct
8 Correct 206 ms 106552 KB Output is correct
9 Correct 211 ms 106712 KB Output is correct
10 Correct 60 ms 87180 KB Output is correct
11 Correct 427 ms 103468 KB Output is correct
12 Correct 479 ms 100796 KB Output is correct
13 Correct 368 ms 104904 KB Output is correct
14 Correct 58 ms 87244 KB Output is correct
15 Correct 397 ms 100856 KB Output is correct
16 Correct 340 ms 99532 KB Output is correct
17 Correct 373 ms 99824 KB Output is correct
18 Correct 392 ms 100300 KB Output is correct
19 Correct 496 ms 103920 KB Output is correct
20 Correct 483 ms 103004 KB Output is correct
21 Correct 251 ms 106616 KB Output is correct
22 Correct 233 ms 102324 KB Output is correct
23 Correct 308 ms 100040 KB Output is correct
24 Correct 288 ms 100048 KB Output is correct
25 Correct 482 ms 107896 KB Output is correct
26 Correct 359 ms 98436 KB Output is correct
27 Correct 331 ms 98436 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 87136 KB Output is correct
2 Correct 72 ms 86900 KB Output is correct
3 Correct 69 ms 88136 KB Output is correct
4 Correct 79 ms 88144 KB Output is correct
5 Correct 74 ms 87756 KB Output is correct
6 Correct 69 ms 88216 KB Output is correct
7 Correct 60 ms 87336 KB Output is correct
8 Correct 206 ms 106552 KB Output is correct
9 Correct 211 ms 106712 KB Output is correct
10 Correct 60 ms 87180 KB Output is correct
11 Correct 427 ms 103468 KB Output is correct
12 Correct 479 ms 100796 KB Output is correct
13 Correct 368 ms 104904 KB Output is correct
14 Correct 58 ms 87244 KB Output is correct
15 Correct 397 ms 100856 KB Output is correct
16 Correct 340 ms 99532 KB Output is correct
17 Correct 373 ms 99824 KB Output is correct
18 Correct 392 ms 100300 KB Output is correct
19 Correct 496 ms 103920 KB Output is correct
20 Correct 483 ms 103004 KB Output is correct
21 Correct 251 ms 106616 KB Output is correct
22 Correct 233 ms 102324 KB Output is correct
23 Correct 308 ms 100040 KB Output is correct
24 Correct 288 ms 100048 KB Output is correct
25 Correct 482 ms 107896 KB Output is correct
26 Correct 359 ms 98436 KB Output is correct
27 Correct 331 ms 98436 KB Output is correct
28 Correct 81 ms 87048 KB Output is correct
29 Correct 79 ms 87540 KB Output is correct
30 Correct 72 ms 87540 KB Output is correct
31 Correct 89 ms 87616 KB Output is correct
32 Correct 75 ms 87284 KB Output is correct
33 Correct 69 ms 87508 KB Output is correct
34 Correct 71 ms 87044 KB Output is correct
35 Correct 194 ms 106392 KB Output is correct
36 Correct 148 ms 103588 KB Output is correct
37 Correct 173 ms 103988 KB Output is correct
38 Correct 58 ms 87084 KB Output is correct
39 Correct 496 ms 103612 KB Output is correct
40 Correct 369 ms 105644 KB Output is correct
41 Correct 525 ms 102792 KB Output is correct
42 Correct 502 ms 102660 KB Output is correct
43 Correct 59 ms 86556 KB Output is correct
44 Correct 398 ms 102024 KB Output is correct
45 Correct 375 ms 99464 KB Output is correct
46 Correct 440 ms 100228 KB Output is correct
47 Correct 537 ms 99224 KB Output is correct
48 Correct 545 ms 103028 KB Output is correct
49 Correct 654 ms 103880 KB Output is correct
50 Correct 586 ms 103504 KB Output is correct
51 Correct 178 ms 104340 KB Output is correct
52 Correct 190 ms 104660 KB Output is correct
53 Correct 157 ms 104424 KB Output is correct
54 Correct 157 ms 104872 KB Output is correct
55 Correct 157 ms 100400 KB Output is correct
56 Correct 307 ms 98296 KB Output is correct
57 Correct 420 ms 103856 KB Output is correct
58 Correct 506 ms 96484 KB Output is correct
59 Correct 360 ms 98412 KB Output is correct