Submission #416501

#	Time	Username	Problem	Language	Result	Execution time	Memory
416501		Blagojce	Inside information (BOI21_servers)	C++11	2.50 / 100	344 ms	25660 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<int, int> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;

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


int n, k;


vector<pii> g[mxn];
void add_edge(int a, int b, int w){
	g[a].pb({b, w});
	g[b].pb({a, w});
}

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

int qry[2*mxn];


bool deleted[mxn];
int sub[mxn];

int cn;
int mark[mxn];
int id;



int tin[mxn];
int tout[mxn];


void dfs0(int u, int p){
	tin[u] = -1e9;
	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] && sub[e.st] > cn/2){
			return dfs1(e.st, u);
		}
	}
	return u;
}

int ans[2*mxn];


int ccen;


void inc(int u, int p, int cw, int mw){
	tin[u] = mw;	
	tout[u] = cw;
	
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && e.nd >= cw){
			inc(e.st, u, e.nd, mw);
		}
	}
}

void dec(int u, int p, int cw, int mw){
	for(auto q : Q[u]){
		if(q.st == ccen){
			if(q.nd >= mw){
				ans[q.nd] = 1;
			}
		}
		else{
			if(mark[q.st] == mark[u] && mw <= tin[q.st] && tout[q.st] <= q.nd){
				ans[q.nd] = 1;
			}
		}
	}
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && e.nd <= cw){
			dec(e.st, u, e.nd, mw);
		}
	}
}


void decompose(int u, int p){
	++id;
	dfs0(u, u);
	cn = sub[u];
	
	int cen = dfs1(u, u);
	ccen = cen;
	
	for(auto e : g[u]){
		if(deleted[e.st]) continue;
		inc(e.st, cen, e.nd, e.nd);
	}
	for(auto e : g[u]){
		if(deleted[e.st]) continue;
		dec(e.st, cen, e.nd, e.nd);
	}
	
	for(auto q : Q[cen]){
		if(tout[q.st] < q.nd){
			ans[q.nd] = 1;
		}
	}
	
	deleted[cen] = true;
	for(auto e : g[u]){
		if(deleted[e.st]) continue;
		decompose(e.st, cen);
	}
}



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

int main(){
	//freopen("in.txt", "r", stdin);
	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