Submission #898956

#	Time	Username	Problem	Language	Result	Execution time	Memory
898956		arashMLG	Inside information (BOI21_servers)	C++17	15 / 100	3546 ms	24504 KiB

servers

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N = 12e4 + 23;
const int LOG = 17;
const ll inf = 1e18;

#define F         first
#define S         second
#define pb        push_back
#define sz(x)     ((int)x.size())
#define all(x)    x.begin(),x.end()
#define lc        (v<<1)
#define rc        ((v<<1)|1)
#define debug(x)  cerr<<#x << " : " << x << endl;

struct query {
	char c;
	int a,b;
	int time;
	query(char C,int A,int B,int TIME) {
		c= C;
		a= A;
		b= B;
		time = TIME;
	}
};

int n,m;
vector<pii> G[N];
vector<query> quer;
int par[N];
int val[N];
int h[N];

void dfsset(int v,int p = -1,int wp=0){ 
	val[v] = wp;
	//debug(v);
	for(auto [u,w] : G[v]) if(u != p) {
		h[u] = h[v] + 1;
		par[u] = v;
		dfsset(u,v,w);
	}
}

int timer= 1;

int lca(int v,int u) {
	if(h[v]< h[u]) swap(v,u);
	int x = h[v]-h[u];
	for(int i = 0 ;i <x; i ++) v = par[v];
	if(v == u) return v;
	while(v != u) {
		v = par[v];
		u = par[u];
	}
	return v;
}

bool check(int a,int b) {
	// a-> b
	if(a == b) return true;
	int l = lca(a,b);
	vector<int> vals1,vals2;
	while(a != l) {
		vals1.pb(val[a]);
		a = par[a];
	}
	while(b != l) {
		vals2.pb(val[b]);
		b = par[b];
	}
	reverse(all(vals2));
	for(int x : vals2) vals1.pb(x);
	return is_sorted(all(vals1)) && vals1.back() <= timer;
}

int32_t main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>m; m+= n-1;
	while(timer <= m) {
		char c; cin>>c;
		assert(c != 'C');
		int a,b; cin>>a>>b;
		quer.emplace_back(c,a,b,timer);
		if(c == 'S') {
			G[a].pb({b,timer});
			G[b].pb({a,timer});
		}
		timer ++;
	}
	dfsset(1);
	timer = 1;
	for(auto q : quer) {
		if(q.c == 'S') {
			timer ++;
			continue;
		}
		int a =q.a,b=q.b;
		cout<< (check(b,a) ? "yes" : "no") << '\n';
		timer ++;
	}
	return 0;
}

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