Submission #573780

#	Time	Username	Problem	Language	Result	Execution time	Memory
573780		amunduzbaev	Inside information (BOI21_servers)	C++17	0 / 100	50 ms	7828 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){
	//~ 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];
			}
		}
		if(tot == 0) return ed[b];
		else return -1;
	}
	
	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";
		if(tot == d[o] - d[b]) return ed[o];
		else return -1;
	}
	
	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];
		}
	}
	
	if(t1 == 0 && t2 == d[o] - d[a] && ed[a] > ed[b]){
		return ed[o];
	} else return -1;
}

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'){
			assert(false);
		}
	}
	
	dfs(1);
	
	for(auto [a, b, t] : q){
		int x = check(a, b);
		//~ cout<<t<<" "<<x<<"\n";
		if((~x && x <= t) || a == b) cout<<"yes\n";
		else cout<<"no\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

*/

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