Submission #401011

#	Time	Username	Problem	Language	Result	Execution time	Memory
401011		errorgorn	Inside information (BOI21_servers)	C++17	50 / 100	486 ms	52672 KiB

servers

#include <bits/stdc++.h>
using namespace std;

#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 node{
	int s,e,m;
	int val=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int j,int k){
		if (s==i && e==j) val+=k;
		else if (j<=m) l->update(i,j,k);
		else if (m<i) r->update(i,j,k);
		else l->update(i,m,k),r->update(m+1,j,k);
	}
	
	int query(int i){
		if (s==e) return val;
		if (i<=m) return val+l->query(i);
		else return val+r->query(i);
	}
} *root=new node(0,200005);

int n,k;
vector<ii> al[120005];
int in[120005];
int out[120005];

int d[120005];
int tkd[120005][20];

int asc[120005];
int dsc[120005];
int w[120005];

int TIME=1;

void dfs(int i,int p){
	in[i]=++TIME;
	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);
	}
	out[i]=TIME;
}

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;

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);
	
	//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<<in[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<out[x]<<" "; cout<<endl;
	
	for (auto &it:Q){
		if (it.c=='S'){
			int temp;
			if (d[it.a]>d[it.b]) temp=it.a;
			else temp=it.b;
			
			root->update(in[temp],out[temp],1);
			
			//cout<<"upd: "<<temp<<endl;
			
			//rep(x,1,n+1) cout<<root->query(in[x])<<" "; cout<<endl;
		}
		else if (it.c=='Q'){
			//cout<<"query: "<<it.a<<" "<<it.b<<endl;
			
			int g=lca(it.a,it.b);
			
			int dist=d[it.a]+d[it.b]-2*d[g];
			int dist2=root->query(in[it.a])
						+root->query(in[it.b])
						-2*root->query(in[g]);
						
			//cout<<dist<<" "<<dist2<<endl;
			
			if (dist!=dist2){
				cout<<"no"<<endl;
				continue;
			}
			
			if (g==it.a){
				if (d[dsc[it.b]]<=d[g]) cout<<"yes"<<endl;
				else cout<<"no"<<endl;
			}
			else if (g==it.b){
				if (d[asc[it.a]]<=d[g]) cout<<"yes"<<endl;
				else cout<<"no"<<endl;
			}
			else{
				bool can=true;
				if (d[dsc[it.b]]>d[g]) can=false;
				if (d[asc[it.a]]>d[g]) can=false;
				
				int b=mov(it.b,d[it.b]-d[g]-1);
				int a=mov(it.a,d[it.a]-d[g]-1);
				if (w[a]<w[b]) can=false;
				
				if (can) cout<<"yes"<<endl;
				else cout<<"no"<<endl;
			}
		}
		else{
			
		}
	}
}

Compilation message (stderr)

servers.cpp: In constructor 'node::node(int, int)':
servers.cpp:25:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 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