oj.uz

Submission #416560

# Submission time Handle Problem Language Result Execution time Memory
416560 2021-06-02T15:35:30 Z Blagojce Inside information (BOI21_servers) C++11
100 / 100
 806 ms 38068 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;

mt19937 _rand(time(NULL));
const int mxn = 2e5;


int n, k;


vector<pii> g[mxn];
void add_edge(int a, int b, int w){
	g[a].pb({b, w});
	g[b].pb({a, w});
}

vector<pii> Q[mxn];
vector<int> C[mxn];

int qry[2*mxn];


bool deleted[mxn];
int sub[mxn];

int cn;


int bit[2*mxn];

void update(int k, int v){
	while(k < 2*mxn){
		bit[k] += v;
		k += k&-k;
	}
}
int sum(int k){
	int s = 0;
	while(k > 0){
		s += bit[k];
		k -= k&-k;
	}
	return s;
}






int tin[mxn];


void dfs0(int u, int p){
	sub[u] = 1;
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		dfs0(e.st, u);
		sub[u] += sub[e.st];
	}
}
int dfs1(int u, int p){
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && sub[e.st] > cn/2){
			return dfs1(e.st, u);
		}
	}
	return u;
}

int ans[2*mxn];


int ccen;

vector<int> updatelist;
void inc(int u, int p, int cw){
	tin[u] = cw;	
	
	update(cw+1, 1);
	updatelist.pb(cw);
	
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && e.nd >= cw){
			inc(e.st, u, e.nd);
		}
	}
}
int active_w;

void dec(int u, int p, int cw){
	for(auto q : Q[u]){
		if(q.st == ccen){
			if(active_w <= q.nd){
				ans[q.nd] = 1;
			}
			continue;
		}
		if(tin[q.st] <= q.nd){
			ans[q.nd] = 1;
		}
	}
	for(auto c : C[u]){
		
		ans[c] += sum(c+1);
		if(active_w <= c) ans[c]++;
	}
	
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && e.nd <= cw){
			dec(e.st, u, e.nd);
		}
	}
}


void clr(int u, int p){
	tin[u] = 1e9;
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		clr(e.st, u);
	}
}

void decompose(int u, int p){
	dfs0(u, u);
	cn = sub[u];
	
	int cen = dfs1(u, u);
	ccen = cen;
	
	sort(all(g[cen]), [](const pii &v1, const pii &v2){
		return v1.nd > v2.nd;
	});
	
	
	for(auto e : g[cen]){
		if(deleted[e.st]) continue;
		active_w = e.nd;
		dec(e.st, cen, e.nd);
		inc(e.st, cen, e.nd);
	}
	
	for(auto q : Q[cen]){
		if(tin[q.st] <= q.nd){
			ans[q.nd] = 1;
		}
	}
	for(auto c : C[cen]){
		ans[c] += sum(c+1);
	}
	
	for(auto e : updatelist){
		update(e+1, -1);
	}
	updatelist.clear();
	clr(cen, cen);
	
	deleted[cen] = true;
	for(auto e : g[cen]){
		if(deleted[e.st]) continue;
		decompose(e.st, cen);
	}
}



void solve(){
	cin >> n >> k;
	fr(i, 0, n+k-1){
		char t;
		cin >> t;
		if(t == 'S'){
			qry[i] = 0;
			int u, v;
			cin >> u >> v;
			--u, --v;
			add_edge(u, v, i);
		}
		else if(t == 'Q'){
			qry[i] = 1;
			int u, v;
			cin >> u >> v;
			--u, --v;
			if(u == v){
				ans[i] = 1;
			}
			else Q[v].pb({u, i});
		}
		else{
			qry[i] = 2;
			int u;
			cin >> u;
			--u;
			C[u].pb(i);
		}
	}
	clr(0, 0);
	decompose(0, -1);
	
	
	fr(i, 0, n+k-1){
		if(qry[i] == 0) continue;
		if(qry[i] == 1){
			if(ans[i] == 1) cout<<"yes"<<endl;
			else cout<<"no"<<endl;
		}
		else{
			cout<<ans[i]+1<<endl;
		}
	}
}

int main(){
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	
}
/*
7 2
S 1 2
S 2 4
S 5 2
S 3 7
S 1 3
S 3 6
Q 6 7
Q 7 6
*/
/*
4 10
S 1 2
S 3 4
S 2 3
Q 1 2
Q 1 3
Q 1 4
Q 2 1
Q 2 3
Q 2 4
Q 3 1
Q 3 2
Q 3 4
Q 4 1
*/

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 222 ms 17604 KB Output is correct
2 Correct 235 ms 17848 KB Output is correct
3 Correct 250 ms 17732 KB Output is correct
4 Correct 231 ms 17836 KB Output is correct
5 Correct 229 ms 17820 KB Output is correct
6 Correct 232 ms 17764 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 222 ms 17604 KB Output is correct
2 Correct 235 ms 17848 KB Output is correct
3 Correct 250 ms 17732 KB Output is correct
4 Correct 231 ms 17836 KB Output is correct
5 Correct 229 ms 17820 KB Output is correct
6 Correct 232 ms 17764 KB Output is correct
7 Correct 224 ms 17552 KB Output is correct
8 Correct 233 ms 18756 KB Output is correct
9 Correct 233 ms 18504 KB Output is correct
10 Correct 236 ms 18876 KB Output is correct
11 Correct 235 ms 18628 KB Output is correct
12 Correct 227 ms 18404 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 215 ms 17652 KB Output is correct
2 Correct 398 ms 26640 KB Output is correct
3 Correct 411 ms 26604 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 215 ms 17652 KB Output is correct
2 Correct 398 ms 26640 KB Output is correct
3 Correct 411 ms 26604 KB Output is correct
4 Correct 221 ms 17648 KB Output is correct
5 Correct 423 ms 29144 KB Output is correct
6 Correct 327 ms 26792 KB Output is correct
7 Correct 323 ms 27052 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 17604 KB Output is correct
2 Correct 556 ms 33740 KB Output is correct
3 Correct 577 ms 33756 KB Output is correct
4 Correct 450 ms 34416 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 17604 KB Output is correct
2 Correct 556 ms 33740 KB Output is correct
3 Correct 577 ms 33756 KB Output is correct
4 Correct 450 ms 34416 KB Output is correct
5 Correct 225 ms 17616 KB Output is correct
6 Correct 593 ms 37240 KB Output is correct
7 Correct 493 ms 37936 KB Output is correct
8 Correct 556 ms 36676 KB Output is correct
9 Correct 557 ms 36676 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 17732 KB Output is correct
2 Correct 425 ms 25840 KB Output is correct
3 Correct 484 ms 24988 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 17732 KB Output is correct
2 Correct 425 ms 25840 KB Output is correct
3 Correct 484 ms 24988 KB Output is correct
4 Correct 223 ms 17640 KB Output is correct
5 Correct 477 ms 29324 KB Output is correct
6 Correct 491 ms 28520 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 214 ms 17636 KB Output is correct
2 Correct 570 ms 33720 KB Output is correct
3 Correct 540 ms 33712 KB Output is correct
4 Correct 453 ms 34488 KB Output is correct
5 Correct 219 ms 17604 KB Output is correct
6 Correct 433 ms 25876 KB Output is correct
7 Correct 485 ms 25028 KB Output is correct
8 Correct 514 ms 25796 KB Output is correct
9 Correct 529 ms 26316 KB Output is correct
10 Correct 590 ms 29632 KB Output is correct
11 Correct 622 ms 28460 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 214 ms 17636 KB Output is correct
2 Correct 570 ms 33720 KB Output is correct
3 Correct 540 ms 33712 KB Output is correct
4 Correct 453 ms 34488 KB Output is correct
5 Correct 219 ms 17604 KB Output is correct
6 Correct 433 ms 25876 KB Output is correct
7 Correct 485 ms 25028 KB Output is correct
8 Correct 514 ms 25796 KB Output is correct
9 Correct 529 ms 26316 KB Output is correct
10 Correct 590 ms 29632 KB Output is correct
11 Correct 622 ms 28460 KB Output is correct
12 Correct 225 ms 17600 KB Output is correct
13 Correct 608 ms 37304 KB Output is correct
14 Correct 500 ms 37952 KB Output is correct
15 Correct 585 ms 36772 KB Output is correct
16 Correct 595 ms 36676 KB Output is correct
17 Correct 235 ms 18500 KB Output is correct
18 Correct 473 ms 29320 KB Output is correct
19 Correct 529 ms 28480 KB Output is correct
20 Correct 537 ms 29540 KB Output is correct
21 Correct 575 ms 29764 KB Output is correct
22 Correct 763 ms 31976 KB Output is correct
23 Correct 806 ms 32652 KB Output is correct
24 Correct 757 ms 31936 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 219 ms 17648 KB Output is correct
2 Correct 233 ms 17836 KB Output is correct
3 Correct 227 ms 17816 KB Output is correct
4 Correct 244 ms 17884 KB Output is correct
5 Correct 235 ms 17704 KB Output is correct
6 Correct 234 ms 17884 KB Output is correct
7 Correct 218 ms 17636 KB Output is correct
8 Correct 397 ms 26640 KB Output is correct
9 Correct 409 ms 26660 KB Output is correct
10 Correct 219 ms 17564 KB Output is correct
11 Correct 525 ms 33624 KB Output is correct
12 Correct 538 ms 33732 KB Output is correct
13 Correct 449 ms 34364 KB Output is correct
14 Correct 218 ms 17608 KB Output is correct
15 Correct 421 ms 25812 KB Output is correct
16 Correct 471 ms 25032 KB Output is correct
17 Correct 486 ms 25792 KB Output is correct
18 Correct 516 ms 26260 KB Output is correct
19 Correct 598 ms 29740 KB Output is correct
20 Correct 642 ms 28356 KB Output is correct
21 Correct 430 ms 26128 KB Output is correct
22 Correct 438 ms 26124 KB Output is correct
23 Correct 471 ms 26112 KB Output is correct
24 Correct 470 ms 26052 KB Output is correct
25 Correct 603 ms 30140 KB Output is correct
26 Correct 531 ms 23936 KB Output is correct
27 Correct 526 ms 23644 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 219 ms 17648 KB Output is correct
2 Correct 233 ms 17836 KB Output is correct
3 Correct 227 ms 17816 KB Output is correct
4 Correct 244 ms 17884 KB Output is correct
5 Correct 235 ms 17704 KB Output is correct
6 Correct 234 ms 17884 KB Output is correct
7 Correct 218 ms 17636 KB Output is correct
8 Correct 397 ms 26640 KB Output is correct
9 Correct 409 ms 26660 KB Output is correct
10 Correct 219 ms 17564 KB Output is correct
11 Correct 525 ms 33624 KB Output is correct
12 Correct 538 ms 33732 KB Output is correct
13 Correct 449 ms 34364 KB Output is correct
14 Correct 218 ms 17608 KB Output is correct
15 Correct 421 ms 25812 KB Output is correct
16 Correct 471 ms 25032 KB Output is correct
17 Correct 486 ms 25792 KB Output is correct
18 Correct 516 ms 26260 KB Output is correct
19 Correct 598 ms 29740 KB Output is correct
20 Correct 642 ms 28356 KB Output is correct
21 Correct 430 ms 26128 KB Output is correct
22 Correct 438 ms 26124 KB Output is correct
23 Correct 471 ms 26112 KB Output is correct
24 Correct 470 ms 26052 KB Output is correct
25 Correct 603 ms 30140 KB Output is correct
26 Correct 531 ms 23936 KB Output is correct
27 Correct 526 ms 23644 KB Output is correct
28 Correct 217 ms 17792 KB Output is correct
29 Correct 234 ms 18724 KB Output is correct
30 Correct 228 ms 18556 KB Output is correct
31 Correct 237 ms 18868 KB Output is correct
32 Correct 235 ms 18628 KB Output is correct
33 Correct 228 ms 18408 KB Output is correct
34 Correct 220 ms 18500 KB Output is correct
35 Correct 378 ms 29096 KB Output is correct
36 Correct 320 ms 26908 KB Output is correct
37 Correct 337 ms 27008 KB Output is correct
38 Correct 223 ms 18484 KB Output is correct
39 Correct 554 ms 37320 KB Output is correct
40 Correct 481 ms 38068 KB Output is correct
41 Correct 559 ms 36760 KB Output is correct
42 Correct 548 ms 36800 KB Output is correct
43 Correct 218 ms 18540 KB Output is correct
44 Correct 458 ms 29256 KB Output is correct
45 Correct 493 ms 28532 KB Output is correct
46 Correct 526 ms 29636 KB Output is correct
47 Correct 528 ms 29788 KB Output is correct
48 Correct 689 ms 31976 KB Output is correct
49 Correct 762 ms 32548 KB Output is correct
50 Correct 709 ms 31952 KB Output is correct
51 Correct 346 ms 27888 KB Output is correct
52 Correct 331 ms 27728 KB Output is correct
53 Correct 337 ms 27424 KB Output is correct
54 Correct 362 ms 27952 KB Output is correct
55 Correct 337 ms 27276 KB Output is correct
56 Correct 426 ms 28352 KB Output is correct
57 Correct 512 ms 31464 KB Output is correct
58 Correct 600 ms 28172 KB Output is correct
59 Correct 500 ms 27204 KB Output is correct