oj.uz

Submission #587197

# Submission time Handle Problem Language Result Execution time Memory
587197 2022-07-01T13:15:50 Z WongChun1234 Inside information (BOI21_servers) C++14
52.5 / 100
 2339 ms 384660 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 (frmnde[j.first][u[i]]>i) continue;
				if (DEBUG) cerr<<i<<":"<<u[i]<<"->"<<j.first<<"@"<<frmnde[j.first][u[i]]<<"\n";
				ans[i]++;
				todo[j.first].push_back({i,{frmnde[j.first][u[i]],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 78 ms 25676 KB Output is correct
2 Correct 629 ms 52036 KB Output is correct
3 Correct 116 ms 30720 KB Output is correct
4 Correct 906 ms 63784 KB Output is correct
5 Correct 849 ms 65392 KB Output is correct
6 Correct 79 ms 29544 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 78 ms 25676 KB Output is correct
2 Correct 629 ms 52036 KB Output is correct
3 Correct 116 ms 30720 KB Output is correct
4 Correct 906 ms 63784 KB Output is correct
5 Correct 849 ms 65392 KB Output is correct
6 Correct 79 ms 29544 KB Output is correct
7 Incorrect 83 ms 26156 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 63 ms 25676 KB Output is correct
2 Correct 329 ms 56560 KB Output is correct
3 Correct 331 ms 56512 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 25676 KB Output is correct
2 Correct 329 ms 56560 KB Output is correct
3 Correct 331 ms 56512 KB Output is correct
4 Correct 61 ms 26060 KB Output is correct
5 Correct 327 ms 57320 KB Output is correct
6 Correct 282 ms 55220 KB Output is correct
7 Correct 251 ms 56232 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 25632 KB Output is correct
2 Correct 1351 ms 326640 KB Output is correct
3 Correct 1329 ms 326504 KB Output is correct
4 Correct 1565 ms 384660 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 25632 KB Output is correct
2 Correct 1351 ms 326640 KB Output is correct
3 Correct 1329 ms 326504 KB Output is correct
4 Correct 1565 ms 384660 KB Output is correct
5 Incorrect 77 ms 26152 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 78 ms 25560 KB Output is correct
2 Correct 1512 ms 333540 KB Output is correct
3 Correct 1412 ms 295360 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 25560 KB Output is correct
2 Correct 1512 ms 333540 KB Output is correct
3 Correct 1412 ms 295360 KB Output is correct
4 Incorrect 75 ms 26140 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 79 ms 25640 KB Output is correct
2 Correct 1282 ms 326500 KB Output is correct
3 Correct 1268 ms 326544 KB Output is correct
4 Correct 1514 ms 384604 KB Output is correct
5 Correct 72 ms 25600 KB Output is correct
6 Correct 1478 ms 333612 KB Output is correct
7 Correct 1395 ms 295560 KB Output is correct
8 Correct 1707 ms 280584 KB Output is correct
9 Correct 1434 ms 236552 KB Output is correct
10 Correct 2021 ms 321972 KB Output is correct
11 Correct 2333 ms 357940 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 79 ms 25640 KB Output is correct
2 Correct 1282 ms 326500 KB Output is correct
3 Correct 1268 ms 326544 KB Output is correct
4 Correct 1514 ms 384604 KB Output is correct
5 Correct 72 ms 25600 KB Output is correct
6 Correct 1478 ms 333612 KB Output is correct
7 Correct 1395 ms 295560 KB Output is correct
8 Correct 1707 ms 280584 KB Output is correct
9 Correct 1434 ms 236552 KB Output is correct
10 Correct 2021 ms 321972 KB Output is correct
11 Correct 2333 ms 357940 KB Output is correct
12 Incorrect 79 ms 26092 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 88 ms 25588 KB Output is correct
2 Correct 585 ms 52004 KB Output is correct
3 Correct 122 ms 30936 KB Output is correct
4 Correct 885 ms 63676 KB Output is correct
5 Correct 805 ms 65456 KB Output is correct
6 Correct 77 ms 29636 KB Output is correct
7 Correct 58 ms 25676 KB Output is correct
8 Correct 309 ms 56488 KB Output is correct
9 Correct 312 ms 56472 KB Output is correct
10 Correct 77 ms 25740 KB Output is correct
11 Correct 1269 ms 326500 KB Output is correct
12 Correct 1284 ms 326684 KB Output is correct
13 Correct 1509 ms 384520 KB Output is correct
14 Correct 73 ms 25580 KB Output is correct
15 Correct 1489 ms 333740 KB Output is correct
16 Correct 1424 ms 295328 KB Output is correct
17 Correct 1718 ms 280720 KB Output is correct
18 Correct 1469 ms 236580 KB Output is correct
19 Correct 2041 ms 321980 KB Output is correct
20 Correct 2339 ms 357976 KB Output is correct
21 Correct 445 ms 67384 KB Output is correct
22 Correct 444 ms 70440 KB Output is correct
23 Correct 1073 ms 155844 KB Output is correct
24 Correct 1063 ms 155216 KB Output is correct
25 Correct 1356 ms 203788 KB Output is correct
26 Correct 1156 ms 190528 KB Output is correct
27 Correct 1085 ms 188408 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 88 ms 25588 KB Output is correct
2 Correct 585 ms 52004 KB Output is correct
3 Correct 122 ms 30936 KB Output is correct
4 Correct 885 ms 63676 KB Output is correct
5 Correct 805 ms 65456 KB Output is correct
6 Correct 77 ms 29636 KB Output is correct
7 Correct 58 ms 25676 KB Output is correct
8 Correct 309 ms 56488 KB Output is correct
9 Correct 312 ms 56472 KB Output is correct
10 Correct 77 ms 25740 KB Output is correct
11 Correct 1269 ms 326500 KB Output is correct
12 Correct 1284 ms 326684 KB Output is correct
13 Correct 1509 ms 384520 KB Output is correct
14 Correct 73 ms 25580 KB Output is correct
15 Correct 1489 ms 333740 KB Output is correct
16 Correct 1424 ms 295328 KB Output is correct
17 Correct 1718 ms 280720 KB Output is correct
18 Correct 1469 ms 236580 KB Output is correct
19 Correct 2041 ms 321980 KB Output is correct
20 Correct 2339 ms 357976 KB Output is correct
21 Correct 445 ms 67384 KB Output is correct
22 Correct 444 ms 70440 KB Output is correct
23 Correct 1073 ms 155844 KB Output is correct
24 Correct 1063 ms 155216 KB Output is correct
25 Correct 1356 ms 203788 KB Output is correct
26 Correct 1156 ms 190528 KB Output is correct
27 Correct 1085 ms 188408 KB Output is correct
28 Incorrect 79 ms 26188 KB Extra information in the output file
29 Halted 0 ms 0 KB -