Submission #828776

#	Time	Username	Problem	Language	Result	Execution time	Memory
828776		QwertyPi	Inside information (BOI21_servers)	C++14	50 / 100	585 ms	56408 KiB

servers

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1.2e5 + 11;
const int LGN = 17;
vector<pair<int, int>> G[MAXN];
int isq[MAXN * 2], ans[MAXN * 2];

void share(int a, int b, int t){
	G[a].push_back({b, t});
	G[b].push_back({a, t});
}

int p[MAXN], anc[LGN][MAXN];
bool _inc[LGN][MAXN], _dec[LGN][MAXN];
int _max[LGN][MAXN], _min[LGN][MAXN];
int c[MAXN], dep[MAXN];

void dfs(int v, int pa = -1){
	if(pa == -1){
		p[v] = anc[0][v] = v; for(int j = 1; j < LGN; j++) anc[j][v] = v;
	}
	for(auto [u, t] : G[v]){
		if(u != pa){
			p[u] = anc[0][u] = v; for(int j = 1; j < LGN; j++) anc[j][u] = anc[j - 1][anc[j - 1][u]]; 
			dep[u] = dep[v] + 1; _max[0][u] = _min[0][u] = t; _inc[0][u] = _dec[0][u] = true; c[u] = t;
			for(int j = 1; j < LGN; j++){
				_max[j][u] = max(_max[j - 1][u], _max[j - 1][anc[j - 1][u]]);
				_min[j][u] = min(_min[j - 1][u], _min[j - 1][anc[j - 1][u]]);
				_inc[j][u] = _inc[j - 1][u] && _inc[j - 1][anc[j - 1][u]] && _max[j - 1][u] <= _min[j - 1][anc[j - 1][u]];
				_dec[j][u] = _dec[j - 1][u] && _dec[j - 1][anc[j - 1][u]] && _min[j - 1][u] >= _max[j - 1][anc[j - 1][u]];
			}
			dfs(u, v);
		}
	}
}
int kth_anc(int u, int k){
	for(int j = LGN - 1; j >= 0; j--){
		if(k & (1 << j)) u = anc[j][u];
	}
	return u;
}
int lca(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	u = kth_anc(u, dep[u] - dep[v]);
	for(int j = LGN - 1; j >= 0; j--){
		if(anc[j][u] != anc[j][v])
			u = anc[j][u], v = anc[j][v];
	}
	return u == v ? u : p[u];
}

bool is_inc(int u, int l){
	int diff = dep[u] - dep[l];
	int d = __lg(diff);
	return _inc[d][u] && _inc[d][kth_anc(u, diff - (1 << d))];
}

bool is_dec(int u, int l){
	int diff = dep[u] - dep[l];
	int d = __lg(diff);
	return _dec[d][u] && _dec[d][kth_anc(u, diff - (1 << d))];
}

struct query_1{
	int a, d, t;
};

struct query_2{
	int d, t;
};

vector<query_1> Q1;
vector<query_2> Q2;

void query(int a, int d, int t){
	Q1.push_back({a, d, t});
}

void count(int d, int t){
	Q2.push_back({d, t});
}

int32_t main(){
	int n, k; cin >> n >> k;
	for(int t = 0; t < n + k - 1; t++){
		char c; cin >> c;
		if(c == 'S'){
			int a, b; cin >> a >> b;
			share(a, b, t);
		}else if(c == 'Q'){
			int a, d; cin >> a >> d;
			query(a, d, t);
			isq[t] = 1;
		}else{
			int d; cin >> d;
			count(d, t);
			isq[t] = 2;
		}
	}

	dfs(1);
	for(auto [a, d, t] : Q1){
		if(a == d){
			ans[t] = true;
			continue;
		}
		int l = lca(a, d);
		ans[t] = true;
		if(l == a){
			ans[t] = is_inc(d, l);
			ans[t] &= c[kth_anc(d, dep[d] - dep[a] - 1)] <= t;
		}else if(l == d){
			ans[t] = is_dec(a, l);
			ans[t] &= c[a] <= t;
		}else{
			ans[t] = is_inc(d, l);
			ans[t] &= is_dec(a, l);
			ans[t] &= c[kth_anc(a, dep[a] - dep[l] - 1)] >= c[kth_anc(d, dep[d] - dep[l] - 1)];
			ans[t] &= c[a] <= t;
		}
	}

	for(int t = 0; t < n + k - 1; t++){
		if(isq[t] == 1){
			cout << (ans[t] ? "yes" : "no") << endl;
		}else if(isq[t] == 2){
			cout << ans[t] << endl;
		}
	}
}

Compilation message (stderr)

servers.cpp: In function 'void dfs(int, int)':
servers.cpp:24:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |  for(auto [u, t] : G[v]){
      |           ^
servers.cpp: In function 'int32_t main()':
servers.cpp:104:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |  for(auto [a, d, t] : Q1){
      |           ^

• 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