Submission #1179668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179668		emptypringlescan	Inside information (BOI21_servers)	C++20	100 / 100	298 ms	81572 KiB

servers

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > adj[120005],down[120005];
vector<int> cent[120005];
int del[120005],sz[120005],par[120005],pd[20][120005],up[20][120005],dep[120005];
pair<int,int> updec[20][120005];
int dfssize(int x, int p){
	sz[x]=1;
	for(auto i:adj[x]){
		if(i.first!=p&&!del[i.first]) sz[x]+=dfssize(i.first,x);
	}
	return sz[x];
}
int find_cent(int x, int p, int tsz){
	for(auto i:adj[x]){
		if(i.first!=p&&!del[i.first]&&sz[i.first]>tsz/2) return find_cent(i.first,x,tsz);
	}
	return x;
}
void dfs(int x, int p, int prev, int c, int st, int d){
	down[c].push_back({st,prev});
	updec[d][x]={st,prev};
	for(auto i:adj[x]){
		if(i.first!=p&&!del[i.first]&&i.second>prev){
			dfs(i.first,x,i.second,c,st,d);
		}
	}
}
void dfs2(int x, int p, int prev, int c, int st, int d){
	up[d][x]=st;
	for(auto i:adj[x]){
		if(i.first!=p&&!del[i.first]&&i.second<prev){
			dfs2(i.first,x,i.second,c,st,d);
		}
	}
}
bool cmp(pair<int,int> a, pair<int,int> b){return a.second<b.second;}
int build(int x, int d, int pr){
	int c=find_cent(x,-1,dfssize(x,-1));
	dep[c]=d;
	par[c]=pr;
	pd[d][c]=c;
	for(int i=d; i>0; i--){
		if(pd[i][c]==-1) break;
		pd[i-1][c]=par[pd[i][c]];
	}
	for(auto i:adj[c]){
		if(!del[i.first]){
			dfs(i.first,c,i.second,c,i.second,d);
			dfs2(i.first,c,i.second,c,i.second,d);
		}
	}
	sort(down[c].begin(),down[c].end(),cmp);
	del[c]=1;
	for(auto i:adj[c]){
		if(!del[i.first]){
			int kid=build(i.first,d+1,c);
			cent[c].push_back(kid);
		}
	}
	return c;
}
int fenw[300005];
void update(int x, int v){
	for(;x<300005;x+=x&-x) fenw[x]+=v;
}
int query(int x){
	int ret=0;
	for(;x;x-=x&-x) ret+=fenw[x];
	return ret;
}
bool cm2p(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b){return a.first.second<b.first.second;}
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(up,-1,sizeof(up));
    memset(par,-1,sizeof(par));
    memset(pd,-1,sizeof(pd));
    for(int j=0; j<20; j++) for(int i=0; i<120005; i++) updec[j][i]={-1,-1};
    int n,k;
    cin >> n >> k;
    vector<pair<pair<int,int>,int> > qu;
    for(int i=0; i<n+k-1; i++){
		char cmd;
		cin >> cmd;
		if(cmd=='S'){
			int a,b;
			cin >> a >> b;
			adj[a].push_back({b,i});
			adj[b].push_back({a,i});
		}
		else if(cmd=='Q'){
			int a,b;
			cin >> a >> b;
			qu.push_back({{a,b},i});
		}
		else{
			int a;
			cin >> a;
			qu.push_back({{-1,a},i});
		}
	}
	build(1,0,-1);/*
	for(int i=1; i<=n; i++){
		cout << i << ": ";
		for(int j=3; j>=0; j--) cout << pd[j][i] << ' ';
		cout << '\n';
	}*/
	int ans[k];
	vector<pair<pair<int,int>,int> > uwu[120005];
	for(int i=0; i<k; i++){
		if(qu[i].first.first==-1){
			ans[i]=1;
			int x=qu[i].first.second;
			uwu[x].push_back({{-1,qu[i].second},i});
			for(int j=dep[x]-1; j>=0; j--){
				if(up[j][x]==-1||up[j][x]>=qu[i].second) continue;
				ans[i]++;
				uwu[pd[j][x]].push_back({{up[j][x],qu[i].second},i});
			}
		}
		else{
			int x=qu[i].first.first,y=qu[i].first.second;
			if(x==y){
				ans[i]=-1;
				continue;
			}
			for(int j=19; j>=0; j--){
				if(pd[j][x]==pd[j][y]&&pd[j][x]!=-1){
					if(j==dep[x]){
						if(up[j][y]!=-1&&up[j][y]<qu[i].second) ans[i]=-1;
						else ans[i]=-2;
					}
					else if(j==dep[y]){
						if(updec[j][x].second!=-1&&updec[j][x].second<qu[i].second) ans[i]=-1;
						else ans[i]=-2;
					}
					else{
						if(up[j][y]!=-1&&updec[j][x].first!=-1&&up[j][y]<updec[j][x].first&&updec[j][x].second<qu[i].second) ans[i]=-1;
						else ans[i]=-2;
					}
					break;
				}
			}
		}
	}
	for(int i=1; i<=n; i++){
		sort(uwu[i].begin(),uwu[i].end(),cm2p);
		int cnt=0;
		vector<int> undo;
		for(auto j:uwu[i]){
			while(cnt<(int)down[i].size()&&down[i][cnt].second<j.first.second){
				update(down[i][cnt].first+1,1);
				undo.push_back(down[i][cnt].first+1);
				cnt++;
			}
			if(j.second==1){
				//cout << i << ' ' << j.first.first << ' ' << j.first.second << '\n';
				//cout << query(j.first.second+2)-(j.first.first>=0?query(j.first.first+1):0) << '\n';
			}
			ans[j.second]+=query(j.first.second+2)-(j.first.first>=0?query(j.first.first+1):0);
		}
		for(int j:undo) update(j,-1);
	}
	for(int i=0; i<k; i++){
		if(ans[i]<0) cout << (ans[i]==-1?"yes":"no") << '\n';
		else cout << ans[i] << '\n';
	}
}
/*6 3
S 1 2
S 1 3
C 1
C 3
S 3 4
S 4 5
C 3
S 1 6*/

• Subtask 1-1: 2 / 2
• Subtask 1-2: 3 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 3 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 5 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 13 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 18 / 18