oj.uz

Submission #587236

# Submission time Handle Problem Language Result Execution time Memory
587236 2022-07-01T14:08:27 Z WongChun1234 Inside information (BOI21_servers) C++14
52.5 / 100
 2597 ms 384608 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,{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 82 ms 25676 KB Output is correct
2 Correct 637 ms 52012 KB Output is correct
3 Correct 138 ms 30824 KB Output is correct
4 Correct 934 ms 63688 KB Output is correct
5 Correct 830 ms 65444 KB Output is correct
6 Correct 82 ms 29500 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 82 ms 25676 KB Output is correct
2 Correct 637 ms 52012 KB Output is correct
3 Correct 138 ms 30824 KB Output is correct
4 Correct 934 ms 63688 KB Output is correct
5 Correct 830 ms 65444 KB Output is correct
6 Correct 82 ms 29500 KB Output is correct
7 Incorrect 83 ms 26180 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 59 ms 25708 KB Output is correct
2 Correct 360 ms 56504 KB Output is correct
3 Correct 409 ms 56560 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 25708 KB Output is correct
2 Correct 360 ms 56504 KB Output is correct
3 Correct 409 ms 56560 KB Output is correct
4 Correct 61 ms 26020 KB Output is correct
5 Correct 339 ms 57224 KB Output is correct
6 Correct 303 ms 55204 KB Output is correct
7 Correct 256 ms 56228 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 25684 KB Output is correct
2 Correct 1361 ms 326460 KB Output is correct
3 Correct 1429 ms 326456 KB Output is correct
4 Correct 1632 ms 384528 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 25684 KB Output is correct
2 Correct 1361 ms 326460 KB Output is correct
3 Correct 1429 ms 326456 KB Output is correct
4 Correct 1632 ms 384528 KB Output is correct
5 Incorrect 85 ms 26192 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 77 ms 25648 KB Output is correct
2 Correct 1655 ms 333600 KB Output is correct
3 Correct 1492 ms 295376 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 25648 KB Output is correct
2 Correct 1655 ms 333600 KB Output is correct
3 Correct 1492 ms 295376 KB Output is correct
4 Incorrect 77 ms 26100 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 81 ms 25576 KB Output is correct
2 Correct 1312 ms 326476 KB Output is correct
3 Correct 1318 ms 326440 KB Output is correct
4 Correct 1613 ms 384560 KB Output is correct
5 Correct 77 ms 25668 KB Output is correct
6 Correct 1559 ms 333668 KB Output is correct
7 Correct 1473 ms 295436 KB Output is correct
8 Correct 1843 ms 280544 KB Output is correct
9 Correct 1562 ms 236408 KB Output is correct
10 Correct 2172 ms 321892 KB Output is correct
11 Correct 2597 ms 357808 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 81 ms 25576 KB Output is correct
2 Correct 1312 ms 326476 KB Output is correct
3 Correct 1318 ms 326440 KB Output is correct
4 Correct 1613 ms 384560 KB Output is correct
5 Correct 77 ms 25668 KB Output is correct
6 Correct 1559 ms 333668 KB Output is correct
7 Correct 1473 ms 295436 KB Output is correct
8 Correct 1843 ms 280544 KB Output is correct
9 Correct 1562 ms 236408 KB Output is correct
10 Correct 2172 ms 321892 KB Output is correct
11 Correct 2597 ms 357808 KB Output is correct
12 Incorrect 95 ms 26216 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 82 ms 25612 KB Output is correct
2 Correct 709 ms 52024 KB Output is correct
3 Correct 119 ms 30796 KB Output is correct
4 Correct 958 ms 63612 KB Output is correct
5 Correct 887 ms 65364 KB Output is correct
6 Correct 88 ms 29492 KB Output is correct
7 Correct 62 ms 25620 KB Output is correct
8 Correct 318 ms 56596 KB Output is correct
9 Correct 358 ms 56444 KB Output is correct
10 Correct 75 ms 25652 KB Output is correct
11 Correct 1358 ms 326560 KB Output is correct
12 Correct 1332 ms 326516 KB Output is correct
13 Correct 1602 ms 384608 KB Output is correct
14 Correct 72 ms 25592 KB Output is correct
15 Correct 1585 ms 333572 KB Output is correct
16 Correct 1556 ms 295508 KB Output is correct
17 Correct 1794 ms 280640 KB Output is correct
18 Correct 1552 ms 236388 KB Output is correct
19 Correct 2224 ms 321876 KB Output is correct
20 Correct 2507 ms 357804 KB Output is correct
21 Correct 437 ms 67380 KB Output is correct
22 Correct 523 ms 70388 KB Output is correct
23 Correct 1164 ms 155840 KB Output is correct
24 Correct 1099 ms 155180 KB Output is correct
25 Correct 1520 ms 203640 KB Output is correct
26 Correct 1278 ms 190384 KB Output is correct
27 Correct 1136 ms 188496 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 82 ms 25612 KB Output is correct
2 Correct 709 ms 52024 KB Output is correct
3 Correct 119 ms 30796 KB Output is correct
4 Correct 958 ms 63612 KB Output is correct
5 Correct 887 ms 65364 KB Output is correct
6 Correct 88 ms 29492 KB Output is correct
7 Correct 62 ms 25620 KB Output is correct
8 Correct 318 ms 56596 KB Output is correct
9 Correct 358 ms 56444 KB Output is correct
10 Correct 75 ms 25652 KB Output is correct
11 Correct 1358 ms 326560 KB Output is correct
12 Correct 1332 ms 326516 KB Output is correct
13 Correct 1602 ms 384608 KB Output is correct
14 Correct 72 ms 25592 KB Output is correct
15 Correct 1585 ms 333572 KB Output is correct
16 Correct 1556 ms 295508 KB Output is correct
17 Correct 1794 ms 280640 KB Output is correct
18 Correct 1552 ms 236388 KB Output is correct
19 Correct 2224 ms 321876 KB Output is correct
20 Correct 2507 ms 357804 KB Output is correct
21 Correct 437 ms 67380 KB Output is correct
22 Correct 523 ms 70388 KB Output is correct
23 Correct 1164 ms 155840 KB Output is correct
24 Correct 1099 ms 155180 KB Output is correct
25 Correct 1520 ms 203640 KB Output is correct
26 Correct 1278 ms 190384 KB Output is correct
27 Correct 1136 ms 188496 KB Output is correct
28 Incorrect 94 ms 26248 KB Extra information in the output file
29 Halted 0 ms 0 KB -