Submission #401408

#	Time	Username	Problem	Language	Result	Execution time	Memory
401408		errorgorn	Inside information (BOI21_servers)	C++17	100 / 100	2345 ms	102992 KiB

servers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
 
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e)?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
struct DSU{
	int p[120005];
	
	DSU(){
		rep(x,0,120005) p[x]=x;
	}
	
	int par(int i){
		if (p[i]==i) return i;
		else return p[i]=par(p[i]);
	}
	
	void unions(int i,int j){
		i=par(i),j=par(j);
		p[i]=j;
	}
} dsu=DSU();
 
int n,k;
vector<ii> al[120005];
 
int d[120005];
int tkd[120005][20];
 
int asc[120005];
int dsc[120005];
int w[120005];
 
void dfs(int i,int p){
	for (auto &it:al[i]){
		if (it.fi==p) continue;
		w[it.fi]=it.se;
		
		asc[it.fi]=dsc[it.fi]=i;
		if (w[it.fi]>w[i]) asc[it.fi]=asc[i];
		else dsc[it.fi]=dsc[i];
		
		d[it.fi]=d[i]+1;
		
		int curr=tkd[it.fi][0]=i;
		rep(x,0,20){
			if (curr==-1) break;
			curr=tkd[it.fi][x+1]=tkd[curr][x];
		}
		
		dfs(it.fi,i);
	}
}
 
int mov(int i,int j){
	rep(bit,0,20) if (j&(1<<bit)){
		i=tkd[i][bit];
	}
	return i;
}
 
int lca(int i,int j){
	if (d[i]<d[j]) swap(i,j);
	i=mov(i,d[i]-d[j]);
	if (i==j) return i;
	
	rep(x,20,0){
		if (tkd[i][x]!=tkd[j][x]) i=tkd[i][x],j=tkd[j][x];
	}
	
	return tkd[i][0];
}
 
struct dat{
	char c;
	int a,b;
};
 
vector<dat> Q;
 
bool reach(int a,int b){ //is a->b decreasing
	int g=lca(a,b);
			
	if (g==a){
		if (d[dsc[b]]<=d[g]) return true;
		else return false;
	}
	else if (g==b){
		if (d[asc[a]]<=d[g]) return true;
		else return false;
	}
	else{
		bool can=true;
		if (d[dsc[b]]>d[g]) can=false;
		if (d[asc[a]]>d[g]) can=false;
		
		b=mov(b,d[b]-d[g]-1);
		a=mov(a,d[a]-d[g]-1);
		if (w[a]<w[b]) can=false;
		
		return can;
	}
}

int last(int a,int b){ 
	int g=lca(a,b);
	
	if (g==a) return w[mov(b,d[b]-d[a]-1)];
	else return w[a];
}

bool used[120005];
int ss[120005];
int centp[120005];

void dfs_sz(int i,int p){
	ss[i]=1;
	for (auto &it:al[i]){
		if (used[it.fi] || it.fi==p) continue;
		dfs_sz(it.fi,i);
		ss[i]+=ss[it.fi];
	}
}

void dfs_c(int i,int p){
	dfs_sz(i,-1);
	
	int currp=i;
	int curr=i;
	int sz=ss[i];
	while (true){
		for (auto &it:al[curr]){
			if (used[it.fi] || it.fi==currp) continue;
			
			if (ss[it.fi]>sz/2){
				currp=curr;
				curr=it.fi;
				goto reloop;
			}
		}
		break;
		reloop:;
	}
	
	centp[curr]=p;
	used[curr]=true;
	
	for (auto &it:al[curr]) if (!used[it.fi]) dfs_c(it.fi,curr);
}

#define indexed_set tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

indexed_set s[120005];

void upd_c(int i,int j){
	int curr=centp[i];
	
	while (curr!=-1){
		if (reach(i,curr) && last(i,curr)==j){
			s[curr].insert(last(curr,i));
			//cout<<"add: "<<curr<<" "<<last(curr,i)<<endl;
		}
		
		curr=centp[curr];
	}
}

int que_c(int i){
	int res=0;
	res+=sz(s[i])+1;
	int curr=centp[i];
	
	while (curr!=-1){
		if (dsu.par(i)==dsu.par(curr) && reach(curr,i)){
			res+=sz(s[curr])-s[curr].order_of_key(last(curr,i)+1)+1;
		}
		
		curr=centp[curr];
	}
	
	return res;
}
 
int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	
	char c;
	int a,b;
	
	int IDX=0;
	rep(x,0,n+k-1){
		cin>>c;
		
		if (c=='S'){
			cin>>a>>b;
			Q.pub({c,a,b});
			al[a].pub(ii(b,IDX));
			al[b].pub(ii(a,IDX));
			IDX++;
		}
		else if (c=='Q'){
			cin>>a>>b;
			Q.pub({c,a,b});
		}
		else{
			cin>>a;
			Q.pub({c,a,0});
		}
	}
	
	memset(tkd,-1,sizeof(tkd));
	asc[1]=dsc[1]=1;
	dfs(1,-1);
	dfs_c(1,-1);
	
	
	//rep(x,1,n+1) cout<<w[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<asc[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<dsc[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<d[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<centp[x]<<" "; cout<<endl;
	
	IDX=0;
	for (auto &it:Q){
		if (it.c=='S'){
			dsu.unions(it.a,it.b);
			
			upd_c(it.a,IDX);
			upd_c(it.b,IDX);
			IDX++;
			//cout<<endl;
		}
		else if (it.c=='Q'){
			if (dsu.par(it.a)==dsu.par(it.b) && 
				reach(it.a,it.b)) cout<<"yes"<<endl;
			else cout<<"no"<<endl;
		}
		else{
			cout<<que_c(it.a)<<endl;
		}
	}
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5