Submission #416560

#	Time	Username	Problem	Language	Result	Execution time	Memory
416560		Blagojce	Inside information (BOI21_servers)	C++11	100 / 100	806 ms	38068 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 bit[2*mxn];

void update(int k, int v){
	while(k < 2*mxn){
		bit[k] += v;
		k += k&-k;
	}
}
int sum(int k){
	int s = 0;
	while(k > 0){
		s += bit[k];
		k -= k&-k;
	}
	return s;
}






int tin[mxn];


void dfs0(int u, int p){
	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;

vector<int> updatelist;
void inc(int u, int p, int cw){
	tin[u] = cw;	
	
	update(cw+1, 1);
	updatelist.pb(cw);
	
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && e.nd >= cw){
			inc(e.st, u, e.nd);
		}
	}
}
int active_w;

void dec(int u, int p, int cw){
	for(auto q : Q[u]){
		if(q.st == ccen){
			if(active_w <= q.nd){
				ans[q.nd] = 1;
			}
			continue;
		}
		if(tin[q.st] <= q.nd){
			ans[q.nd] = 1;
		}
	}
	for(auto c : C[u]){
		
		ans[c] += sum(c+1);
		if(active_w <= c) ans[c]++;
	}
	
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && e.nd <= cw){
			dec(e.st, u, e.nd);
		}
	}
}


void clr(int u, int p){
	tin[u] = 1e9;
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		clr(e.st, u);
	}
}

void decompose(int u, int p){
	dfs0(u, u);
	cn = sub[u];
	
	int cen = dfs1(u, u);
	ccen = cen;
	
	sort(all(g[cen]), [](const pii &v1, const pii &v2){
		return v1.nd > v2.nd;
	});
	
	
	for(auto e : g[cen]){
		if(deleted[e.st]) continue;
		active_w = e.nd;
		dec(e.st, cen, e.nd);
		inc(e.st, cen, e.nd);
	}
	
	for(auto q : Q[cen]){
		if(tin[q.st] <= q.nd){
			ans[q.nd] = 1;
		}
	}
	for(auto c : C[cen]){
		ans[c] += sum(c+1);
	}
	
	for(auto e : updatelist){
		update(e+1, -1);
	}
	updatelist.clear();
	clr(cen, cen);
	
	deleted[cen] = true;
	for(auto e : g[cen]){
		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);
		}
	}
	clr(0, 0);
	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<<ans[i]+1<<endl;
		}
	}
}

int main(){
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	
}
/*
7 2
S 1 2
S 2 4
S 5 2
S 3 7
S 1 3
S 3 6
Q 6 7
Q 7 6
*/
/*
4 10
S 1 2
S 3 4
S 2 3
Q 1 2
Q 1 3
Q 1 4
Q 2 1
Q 2 3
Q 2 4
Q 3 1
Q 3 2
Q 3 4
Q 4 1
*/

• 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