oj.uz

Submission #587238

# Submission time Handle Problem Language Result Execution time Memory
587238 2022-07-01T14:10:54 Z WongChun1234 Inside information (BOI21_servers) C++14
100 / 100
 3396 ms 382304 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=120050;
const int Q=240050;
const bool DEBUG=0;
int n,k,sz[N],u[Q],v[Q],t[N],preord[N],postord[N],pt,ans[Q],bit[Q];
char ty[Q];
bool del[N];
map<int,int> tonde[N],frmnde[N],incen[N];
vector<int> adj[N];
vector<pair<int,pair<int,int>>> todo[N];
void mainprec(int nde,int par){
	preord[nde]=++pt;
	for (int i:adj[nde]) if (i!=par) mainprec(i,nde);
	postord[nde]=pt;
}
bool isa(int a,int b){
	return (preord[a]<=preord[b]&&postord[a]>=postord[b]);
}
int qedge(int a,int b){
	return (isa(a,b)?t[b]:t[a]);
}
void prec(int nde,int par){
	sz[nde]=1;
	for (int i:adj[nde]){
		if (del[i]) continue;
		if (i==par) continue;
		prec(i,nde);
		sz[nde]+=sz[i];
	}
}
int findcen(int nde,int par,int mx){
	for (int i:adj[nde]){
		if (del[i]) continue;
		if (i==par) continue;
		if (sz[i]>mx/2) return findcen(i,nde,mx);
	}
	return nde;
}
void comp(int nde,int par,int smallrt,int bigrt,int mindist,int mxdist){
	if (DEBUG) cerr<<nde<<":"<<par<<" "<<smallrt<<","<<bigrt<<"::"<<mindist<<","<<mxdist<<"\n";
	incen[nde][bigrt]=smallrt;
	tonde[bigrt][nde]=mxdist;
	frmnde[bigrt][nde]=mindist;
	todo[bigrt].push_back({-1,{qedge(smallrt,bigrt),mxdist}});
	for (int i:adj[nde]){
		if (del[i]) continue;
		if (i==par) continue;
		if (qedge(nde,i)>mxdist){
			comp(i,nde,smallrt,bigrt,INT_MIN,qedge(nde,i));
		}else if (qedge(nde,i)<mindist){
			comp(i,nde,smallrt,bigrt,qedge(nde,i),INT_MAX);
		}else{
			comp(i,nde,smallrt,bigrt,INT_MIN,INT_MAX);
		}
	}
}
void dc(int nde){
	prec(nde,nde);
	int cen=findcen(nde,nde,sz[nde]);
	if (DEBUG) cerr<<nde<<":"<<cen<<"uwuuwu\n";
	del[cen]=1;
	for (int i:adj[cen]){
		if (del[i]) continue;
		comp(i,cen,i,cen,qedge(cen,i),qedge(cen,i));
	}
	for (int i:adj[cen]){
		if (del[i]) continue;
		dc(i);
	}
}
bool check(int rt,int v,int u,int id){
	// v->u
	if (u==rt){
		if (frmnde[rt][v]==INT_MIN) return 0;
		return (qedge(rt,incen[v][rt])<=id);
	}else if (v==rt){
		if (tonde[rt][u]==INT_MAX) return 0;
		return (tonde[rt][u]<=id);
	}else{
		if (incen[u][rt]==incen[v][rt]) return 0;
		if (qedge(incen[v][rt],rt)>qedge(incen[u][rt],rt)) return 0;
		if (frmnde[rt][v]==INT_MIN) return 0;
		if (tonde[rt][u]>id) return 0;
		return 1;
	}
}
bool cmp(pair<int,pair<int,int>> a,pair<int,pair<int,int>> b){
	if (a.second.first!=b.second.first) return a.second.first>b.second.first;
	if (a.first!=b.first) return a.first>b.first;
	return a.second.second>b.second.second;
}
void add(int id,int val){
	for (int i=id;i<Q;i+=(i&-i)) bit[i]+=val;
}
int query(int id){
	int ret=0;
	for (int i=id;i;i-=(i&-i)) ret+=bit[i];
	return ret;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>k;
	for (int i=1;i<n+k;i++){
		cin>>ty[i]>>u[i];
		if (ty[i]=='S'){
			cin>>v[i];
			adj[u[i]].push_back(v[i]);
			adj[v[i]].push_back(u[i]);
		}else if (ty[i]=='Q'){
			cin>>v[i];
		}else{
			//???
		}
	}
	mainprec(1,1);
	for (int i=1;i<n+k;i++){
		if (ty[i]!='S') continue;
		if (isa(u[i],v[i])) t[v[i]]=i;
		else t[u[i]]=i;
	}
	dc(1);
	for (int i=1;i<n+k;i++){
		if (ty[i]=='C'){
			ans[i]++;
			todo[u[i]].push_back({i,{INT_MIN,i}});
			for (auto j:incen[u[i]]){
				if (!j.second||j.first==u[i]) continue;
				if (frmnde[j.first][u[i]]==INT_MIN) continue;
				if (qedge(j.first,j.second)>i) continue;
				if (DEBUG) cerr<<i<<":"<<u[i]<<"->"<<j.first<<"@"<<frmnde[j.first][u[i]]<<"\n";
				ans[i]++;
				todo[j.first].push_back({i,{qedge(j.first,j.second),i}});
			}
		}
	}
	for (int i=1;i<=n;i++){
		if (DEBUG) cerr<<i<<"\n";
		sort(todo[i].begin(),todo[i].end(),cmp);
		for (auto j:todo[i]){
			if (DEBUG) cerr<<j.first<<" "<<j.second.first<<" "<<j.second.second<<":"<<query(j.second.second)<<"\n";
			if (j.first==-1) add(j.second.second,1);
			else ans[j.first]+=query(j.second.second);
		}
		for (auto j:todo[i]) if (j.first==-1) add(j.second.second,-1);
	}
	for (int i=1;i<n+k;i++){
		if (ty[i]=='Q'){
			//check if v->u exists
			if (u[i]==v[i]){
				cout<<"yes\n";
				goto skip;
			}
			if (DEBUG) cerr<<v[i]<<",,"<<u[i]<<"\n";
			for (auto j:incen[v[i]]){
				if (!j.second) continue;
				if (DEBUG) cerr<<j.first<<"::"<<j.second<<"a\n";
				if ((!!incen[u[i]][j.first])||j.first==u[i]){
					if (DEBUG) cerr<<v[i]<<"->"<<incen[v[i]][j.first]<<"--"<<j.first<<"--"<<incen[u[i]][j.first]<<"->"<<u[i]<<"\n";
					if (check(j.first,v[i],u[i],i)){
						cout<<"yes\n";
						goto skip;
					}
				}
			}
			if (incen[u[i]][v[i]]){
				if (check(v[i],v[i],u[i],i)){
					cout<<"yes\n";
					goto skip;
				}
			}
			cout<<"no\n";
			skip:;
		}else if (ty[i]=='C'){
			cout<<ans[i]<<"\n";
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 80 ms 25624 KB Output is correct
2 Correct 683 ms 51852 KB Output is correct
3 Correct 122 ms 30712 KB Output is correct
4 Correct 955 ms 63560 KB Output is correct
5 Correct 846 ms 65368 KB Output is correct
6 Correct 83 ms 29388 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 80 ms 25624 KB Output is correct
2 Correct 683 ms 51852 KB Output is correct
3 Correct 122 ms 30712 KB Output is correct
4 Correct 955 ms 63560 KB Output is correct
5 Correct 846 ms 65368 KB Output is correct
6 Correct 83 ms 29388 KB Output is correct
7 Correct 86 ms 26124 KB Output is correct
8 Correct 345 ms 44148 KB Output is correct
9 Correct 114 ms 31520 KB Output is correct
10 Correct 515 ms 52212 KB Output is correct
11 Correct 463 ms 53756 KB Output is correct
12 Correct 78 ms 29808 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 25628 KB Output is correct
2 Correct 336 ms 55160 KB Output is correct
3 Correct 332 ms 55132 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 25628 KB Output is correct
2 Correct 336 ms 55160 KB Output is correct
3 Correct 332 ms 55132 KB Output is correct
4 Correct 64 ms 26064 KB Output is correct
5 Correct 332 ms 56236 KB Output is correct
6 Correct 274 ms 55020 KB Output is correct
7 Correct 257 ms 55844 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 25656 KB Output is correct
2 Correct 1343 ms 324432 KB Output is correct
3 Correct 1277 ms 323288 KB Output is correct
4 Correct 1548 ms 382216 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 25656 KB Output is correct
2 Correct 1343 ms 324432 KB Output is correct
3 Correct 1277 ms 323288 KB Output is correct
4 Correct 1548 ms 382216 KB Output is correct
5 Correct 81 ms 25412 KB Output is correct
6 Correct 1796 ms 325800 KB Output is correct
7 Correct 1802 ms 347396 KB Output is correct
8 Correct 2240 ms 324364 KB Output is correct
9 Correct 2233 ms 324408 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 24876 KB Output is correct
2 Correct 1527 ms 330568 KB Output is correct
3 Correct 1442 ms 292296 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 24876 KB Output is correct
2 Correct 1527 ms 330568 KB Output is correct
3 Correct 1442 ms 292296 KB Output is correct
4 Correct 76 ms 25408 KB Output is correct
5 Correct 1994 ms 324164 KB Output is correct
6 Correct 1986 ms 299972 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 77 ms 24924 KB Output is correct
2 Correct 1289 ms 323392 KB Output is correct
3 Correct 1278 ms 323384 KB Output is correct
4 Correct 1525 ms 381620 KB Output is correct
5 Correct 76 ms 24796 KB Output is correct
6 Correct 1509 ms 330664 KB Output is correct
7 Correct 1390 ms 292248 KB Output is correct
8 Correct 1757 ms 278448 KB Output is correct
9 Correct 1464 ms 233340 KB Output is correct
10 Correct 2074 ms 318640 KB Output is correct
11 Correct 2380 ms 355848 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 77 ms 24924 KB Output is correct
2 Correct 1289 ms 323392 KB Output is correct
3 Correct 1278 ms 323384 KB Output is correct
4 Correct 1525 ms 381620 KB Output is correct
5 Correct 76 ms 24796 KB Output is correct
6 Correct 1509 ms 330664 KB Output is correct
7 Correct 1390 ms 292248 KB Output is correct
8 Correct 1757 ms 278448 KB Output is correct
9 Correct 1464 ms 233340 KB Output is correct
10 Correct 2074 ms 318640 KB Output is correct
11 Correct 2380 ms 355848 KB Output is correct
12 Correct 78 ms 25860 KB Output is correct
13 Correct 1800 ms 326020 KB Output is correct
14 Correct 1779 ms 347388 KB Output is correct
15 Correct 2220 ms 324452 KB Output is correct
16 Correct 2208 ms 324628 KB Output is correct
17 Correct 78 ms 26084 KB Output is correct
18 Correct 1981 ms 324276 KB Output is correct
19 Correct 1969 ms 299944 KB Output is correct
20 Correct 2104 ms 262676 KB Output is correct
21 Correct 1947 ms 239972 KB Output is correct
22 Correct 3372 ms 316400 KB Output is correct
23 Correct 2874 ms 319344 KB Output is correct
24 Correct 2198 ms 308576 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 81 ms 25708 KB Output is correct
2 Correct 627 ms 50772 KB Output is correct
3 Correct 117 ms 29516 KB Output is correct
4 Correct 899 ms 62368 KB Output is correct
5 Correct 822 ms 64204 KB Output is correct
6 Correct 80 ms 29404 KB Output is correct
7 Correct 61 ms 25664 KB Output is correct
8 Correct 339 ms 54952 KB Output is correct
9 Correct 328 ms 54872 KB Output is correct
10 Correct 76 ms 24932 KB Output is correct
11 Correct 1290 ms 324460 KB Output is correct
12 Correct 1298 ms 324496 KB Output is correct
13 Correct 1542 ms 382304 KB Output is correct
14 Correct 76 ms 24908 KB Output is correct
15 Correct 1500 ms 331700 KB Output is correct
16 Correct 1458 ms 293484 KB Output is correct
17 Correct 1805 ms 278644 KB Output is correct
18 Correct 1503 ms 234584 KB Output is correct
19 Correct 2091 ms 319800 KB Output is correct
20 Correct 2406 ms 355684 KB Output is correct
21 Correct 433 ms 65040 KB Output is correct
22 Correct 447 ms 67980 KB Output is correct
23 Correct 1064 ms 153840 KB Output is correct
24 Correct 1058 ms 152876 KB Output is correct
25 Correct 1358 ms 201648 KB Output is correct
26 Correct 1176 ms 188072 KB Output is correct
27 Correct 1113 ms 186112 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 81 ms 25708 KB Output is correct
2 Correct 627 ms 50772 KB Output is correct
3 Correct 117 ms 29516 KB Output is correct
4 Correct 899 ms 62368 KB Output is correct
5 Correct 822 ms 64204 KB Output is correct
6 Correct 80 ms 29404 KB Output is correct
7 Correct 61 ms 25664 KB Output is correct
8 Correct 339 ms 54952 KB Output is correct
9 Correct 328 ms 54872 KB Output is correct
10 Correct 76 ms 24932 KB Output is correct
11 Correct 1290 ms 324460 KB Output is correct
12 Correct 1298 ms 324496 KB Output is correct
13 Correct 1542 ms 382304 KB Output is correct
14 Correct 76 ms 24908 KB Output is correct
15 Correct 1500 ms 331700 KB Output is correct
16 Correct 1458 ms 293484 KB Output is correct
17 Correct 1805 ms 278644 KB Output is correct
18 Correct 1503 ms 234584 KB Output is correct
19 Correct 2091 ms 319800 KB Output is correct
20 Correct 2406 ms 355684 KB Output is correct
21 Correct 433 ms 65040 KB Output is correct
22 Correct 447 ms 67980 KB Output is correct
23 Correct 1064 ms 153840 KB Output is correct
24 Correct 1058 ms 152876 KB Output is correct
25 Correct 1358 ms 201648 KB Output is correct
26 Correct 1176 ms 188072 KB Output is correct
27 Correct 1113 ms 186112 KB Output is correct
28 Correct 82 ms 26192 KB Output is correct
29 Correct 292 ms 44056 KB Output is correct
30 Correct 102 ms 31448 KB Output is correct
31 Correct 444 ms 52164 KB Output is correct
32 Correct 441 ms 53844 KB Output is correct
33 Correct 70 ms 29848 KB Output is correct
34 Correct 60 ms 26024 KB Output is correct
35 Correct 309 ms 57432 KB Output is correct
36 Correct 278 ms 55132 KB Output is correct
37 Correct 243 ms 56264 KB Output is correct
38 Correct 77 ms 26188 KB Output is correct
39 Correct 1777 ms 325800 KB Output is correct
40 Correct 1804 ms 347468 KB Output is correct
41 Correct 2308 ms 324344 KB Output is correct
42 Correct 2414 ms 324448 KB Output is correct
43 Correct 79 ms 26132 KB Output is correct
44 Correct 2202 ms 324260 KB Output is correct
45 Correct 2113 ms 299972 KB Output is correct
46 Correct 2293 ms 262516 KB Output is correct
47 Correct 2009 ms 239916 KB Output is correct
48 Correct 3396 ms 316444 KB Output is correct
49 Correct 2852 ms 319144 KB Output is correct
50 Correct 2226 ms 308440 KB Output is correct
51 Correct 374 ms 66840 KB Output is correct
52 Correct 282 ms 58312 KB Output is correct
53 Correct 281 ms 56536 KB Output is correct
54 Correct 306 ms 56352 KB Output is correct
55 Correct 366 ms 66056 KB Output is correct
56 Correct 1056 ms 158448 KB Output is correct
57 Correct 1283 ms 203000 KB Output is correct
58 Correct 2001 ms 205976 KB Output is correct
59 Correct 1210 ms 188432 KB Output is correct