oj.uz

Submission #416553

# Submission time Handle Problem Language Result Execution time Memory
416553 2021-06-02T15:21:27 Z Blagojce Inside information (BOI21_servers) C++11
50 / 100
 591 ms 36460 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 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;


void inc(int u, int p, int cw){
	tin[u] = 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 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);
	}
	//cout<<cen+1<<endl;
	
	for(auto q : Q[cen]){
		//cout<<"."<<q.st+1<<' '<<q.nd<<' '<<tin[q.st]<<endl;
		
		if(tin[q.st] <= q.nd){
			ans[q.nd] = 1;
		}
	}
	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<<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 212 ms 17184 KB Output is correct
2 Correct 225 ms 18752 KB Output is correct
3 Correct 219 ms 18720 KB Output is correct
4 Correct 229 ms 18712 KB Output is correct
5 Correct 238 ms 19084 KB Output is correct
6 Correct 225 ms 18880 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 212 ms 17184 KB Output is correct
2 Correct 225 ms 18752 KB Output is correct
3 Correct 219 ms 18720 KB Output is correct
4 Correct 229 ms 18712 KB Output is correct
5 Correct 238 ms 19084 KB Output is correct
6 Correct 225 ms 18880 KB Output is correct
7 Incorrect 206 ms 18036 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 214 ms 17260 KB Output is correct
2 Correct 378 ms 24728 KB Output is correct
3 Correct 362 ms 24692 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 214 ms 17260 KB Output is correct
2 Correct 378 ms 24728 KB Output is correct
3 Correct 362 ms 24692 KB Output is correct
4 Incorrect 203 ms 17236 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 226 ms 17204 KB Output is correct
2 Correct 527 ms 36096 KB Output is correct
3 Correct 555 ms 36208 KB Output is correct
4 Correct 411 ms 36420 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 17204 KB Output is correct
2 Correct 527 ms 36096 KB Output is correct
3 Correct 555 ms 36208 KB Output is correct
4 Correct 411 ms 36420 KB Output is correct
5 Incorrect 205 ms 18040 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 211 ms 17184 KB Output is correct
2 Correct 399 ms 28064 KB Output is correct
3 Correct 444 ms 27424 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 17184 KB Output is correct
2 Correct 399 ms 28064 KB Output is correct
3 Correct 444 ms 27424 KB Output is correct
4 Incorrect 202 ms 18212 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 215 ms 17204 KB Output is correct
2 Correct 515 ms 36132 KB Output is correct
3 Correct 527 ms 36192 KB Output is correct
4 Correct 388 ms 36460 KB Output is correct
5 Correct 213 ms 18244 KB Output is correct
6 Correct 369 ms 28128 KB Output is correct
7 Correct 428 ms 27412 KB Output is correct
8 Correct 465 ms 28648 KB Output is correct
9 Correct 479 ms 28616 KB Output is correct
10 Correct 526 ms 31940 KB Output is correct
11 Correct 539 ms 31104 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 215 ms 17204 KB Output is correct
2 Correct 515 ms 36132 KB Output is correct
3 Correct 527 ms 36192 KB Output is correct
4 Correct 388 ms 36460 KB Output is correct
5 Correct 213 ms 18244 KB Output is correct
6 Correct 369 ms 28128 KB Output is correct
7 Correct 428 ms 27412 KB Output is correct
8 Correct 465 ms 28648 KB Output is correct
9 Correct 479 ms 28616 KB Output is correct
10 Correct 526 ms 31940 KB Output is correct
11 Correct 539 ms 31104 KB Output is correct
12 Incorrect 206 ms 18000 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 221 ms 17200 KB Output is correct
2 Correct 225 ms 18848 KB Output is correct
3 Correct 221 ms 18632 KB Output is correct
4 Correct 225 ms 18884 KB Output is correct
5 Correct 225 ms 19140 KB Output is correct
6 Correct 226 ms 18884 KB Output is correct
7 Correct 214 ms 18312 KB Output is correct
8 Correct 369 ms 27556 KB Output is correct
9 Correct 369 ms 27520 KB Output is correct
10 Correct 214 ms 18116 KB Output is correct
11 Correct 515 ms 36020 KB Output is correct
12 Correct 507 ms 36044 KB Output is correct
13 Correct 387 ms 36432 KB Output is correct
14 Correct 213 ms 18116 KB Output is correct
15 Correct 370 ms 27992 KB Output is correct
16 Correct 427 ms 27484 KB Output is correct
17 Correct 469 ms 28708 KB Output is correct
18 Correct 484 ms 28564 KB Output is correct
19 Correct 524 ms 31828 KB Output is correct
20 Correct 526 ms 31088 KB Output is correct
21 Correct 387 ms 28212 KB Output is correct
22 Correct 402 ms 28188 KB Output is correct
23 Correct 437 ms 28376 KB Output is correct
24 Correct 428 ms 28360 KB Output is correct
25 Correct 591 ms 32068 KB Output is correct
26 Correct 501 ms 26436 KB Output is correct
27 Correct 475 ms 26132 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 221 ms 17200 KB Output is correct
2 Correct 225 ms 18848 KB Output is correct
3 Correct 221 ms 18632 KB Output is correct
4 Correct 225 ms 18884 KB Output is correct
5 Correct 225 ms 19140 KB Output is correct
6 Correct 226 ms 18884 KB Output is correct
7 Correct 214 ms 18312 KB Output is correct
8 Correct 369 ms 27556 KB Output is correct
9 Correct 369 ms 27520 KB Output is correct
10 Correct 214 ms 18116 KB Output is correct
11 Correct 515 ms 36020 KB Output is correct
12 Correct 507 ms 36044 KB Output is correct
13 Correct 387 ms 36432 KB Output is correct
14 Correct 213 ms 18116 KB Output is correct
15 Correct 370 ms 27992 KB Output is correct
16 Correct 427 ms 27484 KB Output is correct
17 Correct 469 ms 28708 KB Output is correct
18 Correct 484 ms 28564 KB Output is correct
19 Correct 524 ms 31828 KB Output is correct
20 Correct 526 ms 31088 KB Output is correct
21 Correct 387 ms 28212 KB Output is correct
22 Correct 402 ms 28188 KB Output is correct
23 Correct 437 ms 28376 KB Output is correct
24 Correct 428 ms 28360 KB Output is correct
25 Correct 591 ms 32068 KB Output is correct
26 Correct 501 ms 26436 KB Output is correct
27 Correct 475 ms 26132 KB Output is correct
28 Incorrect 201 ms 18024 KB Extra information in the output file
29 Halted 0 ms 0 KB -