제출 #587236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587236		WongChun1234	Inside information (BOI21_servers)	C++14	52.50 / 100	2597 ms	384608 KiB

servers

#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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5