Submission #416073

#	Time	Username	Problem	Language	Result	Execution time	Memory
416073		Blagojce	Inside information (BOI21_servers)	C++11	2.50 / 100	447 ms	54868 KiB

servers

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;

mt19937 _rand(time(NULL));
const int mxn = 4e5;


int n, k;

vector<pii> g[mxn];

vector<pii> Q[mxn];
vector<int> C[mxn];


bool deleted[mxn];

int sub[mxn];

int mark[mxn];

int id;

int locn;


int ti[mxn];
int tout[mxn];


void dfs0(int u, int p){
	ti[u] = tout[u] = -1e9;
	
	
	mark[u] = id;
	
	sub[u] = 1;
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		dfs0(e.st, u);
		sub[u] += sub[e.st];
	}
}

int dfs1(int u, int p){
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		if(sub[e.st] > locn / 2){
			return dfs1(e.st, u);
		}
	}
	return u;
}


int ccen;


void dfs2(int u, int p, int w, int wmin){
	ti[u] = wmin;
	tout[u] = w;
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		
		if(e.nd > w){
			dfs2(e.st, u, e.nd, wmin);
		}
	}
}
string ans[mxn];


void dfs3(int u, int p, int w, int wmax){
	for(auto e : Q[u]){
		if(e.st == ccen){
			if(e.nd > wmax){
				ans[e.nd] = "yes";
			}
		}
		else{
			if(mark[u] != mark[e.st]) continue;
			
			if(e.nd > tout[e.st] && ti[e.st] > wmax){
				ans[e.nd] = "yes";
			}
		}
	}
	
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		
		if(e.nd < w){
			dfs3(e.st, u, e.nd, wmax);
		}
	}
}


void decompose(int u, int p){
	++id;
	dfs0(u, u);
	
	locn = sub[u];
	int cen = dfs1(u, u);
	ccen = cen;
	
	for(auto e : g[cen]){
		if(deleted[e.st]) continue;
		dfs2(e.st, cen, e.nd, e.nd);
	}
	
	for(auto e : g[cen]){
		if(deleted[e.st]) continue;
		dfs3(e.st, cen, e.nd, e.nd);
	}
	
	for(auto e : Q[u]){
		
		if(mark[e.st] != mark[cen]) continue;
		
		if(tout[e.st] < e.nd){
			ans[e.nd] = "yes";
		}
		
	}
	
	
	deleted[cen] = true;
	for(auto e : g[cen]){
		if(deleted[e.st]) continue;
		decompose(e.st, cen);
	}
}


bool qry[mxn];

void solve(){
	cin >> n >> k;
	fr(i, 0, n+k-1){
		ans[i] = "0";
		char t;
		cin >> t;
		if(t == 'S'){
			int u, v;
			cin >> u >> v;
			--u, --v;
			
			g[u].pb({v, i});
			g[v].pb({u, i});
		}
		else if(t == 'Q'){
			qry[i] = true;
			ans[i] = "no";
			int u, v;
			cin >> u >> v;
			if(u == v){
				ans[i] = "yes";
			}
			--u, --v;
			Q[v].pb({u, i});
		}
		else{
			qry[i] = true;
			
			int u;
			cin >> u;
			C[u].pb(i);
		}
	}
	decompose(0, 0);
	
	fr(i, 0, n+k-1){
		if(!qry[i]) continue;
		cout<<ans[i]<<endl;
	}
	
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	
}

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