Submission #574220

#	Time	Username	Problem	Language	Result	Execution time	Memory
574220		amunduzbaev	Inside information (BOI21_servers)	C++17	50 / 100	391 ms	53364 KiB

servers

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

#define ar array

const int N = 2e5 + 5;
vector<ar<int, 2>> edges[N];
int par[N][20], ed[N], lift[N][20];
int tin[N], tout[N], t, d[N];

void dfs(int u){
	tin[u] = ++t;
	lift[u][0] = (ed[u] > ed[par[u][0]]);
	for(int j=1;j<20;j++){
		par[u][j] = par[par[u][j-1]][j-1];
		lift[u][j] = lift[u][j-1] + lift[par[u][j-1]][j-1];
	}
	
	for(auto x : edges[u]){
		if(x[0] == par[u][0]) continue;
		par[x[0]][0] = u, ed[x[0]] = x[1];
		d[x[0]] = d[u] + 1;
		dfs(x[0]);
	}
	tout[u] = t;
}

bool is(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

int check(int a, int b, int t){
	if(a == b) return true;
	//~ cout<<a<<" "<<b<<" "<<is(a, b)<<" "<<is(b, a)<<"\n";
	if(is(a, b)){
		int tot = 0;
		for(int j=19;~j;j--){
			if(!is(par[b][j], a)){
				tot += lift[b][j];
				b = par[b][j];
			}
		}
		return (!tot && ed[b] <= t);
	}
	
	if(is(b, a)){
		swap(a, b);
		int tot = 0, o = b;
		for(int j=19;~j;j--){
			if(!is(par[b][j], a)){
				tot += lift[b][j];
				b = par[b][j];
			}
		}
		//~ cout<<tot<<" "<<d[o] - d[b]<<" "<<ed[o]<<"\n";
		return (tot == d[o] - d[b] && ed[o] <= t);
	}
	
	int t1 = 0, t2 = 0, o = a;
	for(int j=19;~j;j--){
		if(!is(par[b][j], a)){
			t1 += lift[b][j];
			b = par[b][j];
		}
		
		if(!is(par[a][j], b)){
			t2 += lift[a][j];
			a = par[a][j];
		}
	}
	//~ cout<<a<<" "<<b<<"\n";
	//~ cout<<t1<<" "<<t2<<" "<<d[a] - d[o]<<" "<<ed[a]<<" "<<ed[b]<<" "<<ed[o]<<"\n";
	return (t1 == 0 && t2 == d[o] - d[a] && ed[a] > ed[b] && ed[o] <= t);
}

struct BIT{
	int tree[N];
	void add(int i, int v){
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){
		int r = 0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
	
	int get(int l, int r){
		return get(r) - get(l - 1);
	}
}tree;

int res[N], used[N], sub[N];
int to[N], ver[N], pos[N];
vector<int> qq[N], tt, tot;
int face[N];

void dfs1(int u, int p = -1){
	sub[u] = 1;
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		pos[x[1]] = x[0];
		to[x[0]] = x[1], dfs1(x[0], u);
		sub[u] += sub[x[0]];
	}
}

int cen(int u, int n, int p = -1){
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		if(sub[x[0]] * 2 > n) return cen(x[0], n, u);
	} return u;
}

void dfs2(int u, int inc = 1, int dec = 1, int p = -1){
	//~ cout<<u<<" "<<inc<<" "<<dec<<"\n";
	if(dec){
		tt.insert(tt.end(), qq[u].begin(), qq[u].end());
		for(auto x : qq[u]) res[x]++;
	}
	if(inc){
		tot.push_back(to[u]);
	}
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		face[x[0]] = face[u];
		dfs2(x[0], inc & (to[u] < x[1]), dec & (to[u] > x[1]), u);
	}
}

void dec(int u){
	dfs1(u);
	u = cen(u, sub[u]);
	dfs1(u);
	//~ cout<<u<<"\n";
	
	tt.clear(), tot.clear();
	for(auto x : edges[u]){
		if(used[x[0]]) continue;
		face[x[0]] = x[0];
		dfs2(x[0], 1, 1, u);
	}
	
	sort(tt.begin(), tt.end());
	sort(tot.begin(), tot.end());
	sort(qq[u].begin(), qq[u].end());
	
	for(auto x : qq[u]){
		int cc = upper_bound(tot.begin(), tot.end(), x) - tot.begin();
		res[x] += cc;
	}
	
	int j = 0;
	for(auto x : tt){ 
		while(j < (int)tot.size() && tot[j] < x){
			tree.add(face[pos[tot[j]]], 1);
			j++;
		}
		
		res[x] += tree.get(face[ver[x]] + 1, N - 1);
	}
	
	for(int l=0;l<j;l++) tree.add(face[pos[tot[l]]], -1);
	used[u] = 1;
	for(auto x : edges[u]){
		if(used[x[0]]) continue;
		dec(x[0]);
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<ar<int, 3>> q;
	for(int i=1;i<n + m;i++){
		char c; cin>>c;
		if(c == 'S'){
			int a, b; cin>>a>>b;
			edges[a].push_back({b, i});
			edges[b].push_back({a, i});
		} if(c == 'Q') {
			int a, b; cin>>a>>b;
			q.push_back({a, b, i});
		} if(c == 'C'){
			int v; cin>>v;
			qq[v].push_back(i);
			ver[i] = v;
			q.push_back({-1, v, i});
		}
	}
	
	par[1][0] = 1;
	dfs(1);
	dec(1);
	//~ int cnt = 0;
	//~ function<void(int, int, int, int)> dfs = [&](int u, int t, int p, int ed){
		//~ cnt++;
		//~ for(auto x : edges[u]){
			//~ if(x[0] == p || x[1] > t || x[1] <= ed) continue;
			//~ dfs(x[0], t, u, x[1]);
		//~ }
	//~ };
	
	for(auto [a, b, t] : q){
		if(~a){
			if(check(a, b, t)) cout<<"yes\n";
			else cout<<"no\n";
		} else { 
			cout<<++res[t]<<"\n";
		}
	}
}

/*

6 3
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5

5 1
S 5 4
S 4 1
S 1 2
S 2 3
Q 3 5

*/

• 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