Submission #533107

#	Time	Username	Problem	Language	Result	Execution time	Memory
533107		shayanebrahimi	Inside information (BOI21_servers)	C++14	5 / 100	303 ms	41668 KiB

servers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl                        '\n'
#define debug(e)                    cerr << #e << ": " <<  e << endl;
#define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll MOD=1e9+7;//998244353//1e9+9//1111211111;
//ll tavmd(ll a,ll b){if(b==0){return 1;}if(b%2==0){ll x=tavmd(a,b/2);return(x*x)%MOD;}else{return(a%MOD*tavmd(a,b-1)%MOD)%MOD;}}
const ll MAXN=2e5+10;
const ll INF=8e18;
const ll LOG=30;
vector<pair<ll,ll>>adj[MAXN],Q[MAXN];
vector<ll>C[MAXN],updl;
ll qq[2*MAXN],sub[MAXN],bit[2*MAXN],tin[MAXN],ans[MAXN],n,k,cn,ccen,xy;
bool mark[MAXN];
void upd(ll k,ll v){
	while(k<2*MAXN){
		bit[k]+=v;
		k+=k&-k;
	}
}
ll sum(ll k){
	ll s=0;
	while(k>0){
		s+=bit[k];
		k-=k&-k;
	}
	return s;
}
void dfs0(ll u,ll p){
	sub[u]=1;
	for(auto e:adj[u]){
		if(e.first==p||mark[e.first])
                  continue;
		dfs0(e.first,u);
		sub[u]+=sub[e.first];
	}
}
int dfs1(ll u,ll p){
	for(auto e:adj[u]){
		if(e.first!=p&&!mark[e.first]&&sub[e.first]>cn/2){
			return dfs1(e.first,u);
		}
	}
	return u;
}
void inc(ll u,ll p,ll cw){
	tin[u]=cw;
	upd(cw+1,1);
	updl.push_back(cw);
	for(auto e:adj[u]){
		if(e.first!=p&&!mark[e.first]&&e.second>=cw){
			inc(e.first,u,e.second);
		}
	}
}
void dec(ll u,ll p,ll cw){
	for(auto q:Q[u]){
		if(q.first==ccen){
			if(xy<=q.second){
				ans[q.second]=1;
			}
			continue;
		}
		if(tin[q.first]<=q.second){
			ans[q.second]=1;
		}
	}
	for(auto c:C[u]){
		ans[c]+=sum(c+1);
		if(xy<=c)
                  ans[c]++;
	}
	for(auto e:adj[u]){
		if(e.first!=p&&!mark[e.first]&&e.second<=cw){
			dec(e.first,u,e.second);
		}
	}
}
void dfs4(ll u,ll p){
	tin[u]=INF;
	for(auto e:adj[u]){
		if(e.first==p||mark[e.first])
                  continue;
		dfs4(e.first,u);
	}
}
void decompose(ll u,ll p){
	dfs0(u,u);
	cn=sub[u];
	ll cen=dfs1(u, u);
	ccen=cen;
	sort(adj[cen].begin(),adj[cen].end(),[](const pair<ll,ll>&v1,const pair<ll,ll>&v2){
		return v1.second>v2.second;
	});
	for(auto e:adj[cen]){
		if(mark[e.first])
                  continue;
		xy=e.second;
		dec(e.first,cen,e.second);
		inc(e.first,cen,e.second);
	}
	for(auto q:Q[cen]){
		if(tin[q.first]<=q.second){
			ans[q.second]=1;
		}
	}
	for(auto c:C[cen]){
		ans[c]+=sum(c+1);
	}
	for(auto e:updl){
		upd(e+1,-1);
	}
	updl.clear();
	dfs4(cen,cen);
	mark[cen]=true;
	for(auto e:adj[cen]){
		if(mark[e.first])
                  continue;
		decompose(e.first,cen);
	}
}
int main(){
    fast_io;
	cin>>n>>k;
	for(int i=0;i<n+k-1;i++){
		char t;
		cin>>t;
		if(t=='S'){
			qq[i]=0;
			ll u,v;
			cin>>u>>v;
			u--;
			v--;
                  adj[u].push_back({v,i});
                  adj[v].push_back({u,i});
		}
		else if(t=='Q'){
			qq[i]=1;
			ll u,v;
			cin>>u>>v;
			u--;
			v--;
			if(u==v){
				ans[i]=1;
			}
			else
                        Q[v].push_back({u,i});
		}
		else{
			qq[i]=2;
			ll u;
			cin>>u;
			u--;
			C[u].push_back(i);
		}
	}
	dfs4(0,0);
	decompose(0,-1);
	for(int i=0;i<n+k-1;i++){
		if(qq[i]==0)
                  continue;
		if(qq[i]==1){
			if(ans[i]==1)
                        cout<<"yes"<<endl;
			else
                        cout<<"no"<<endl;
		}
		else{
			cout<<ans[i]+1<<endl;
		}
	}
    return 0;
}

Compilation message (stderr)

servers.cpp:6:9: warning: ISO C++11 requires whitespace after the macro name
    6 | #define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
      |         ^~~~~~~

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