제출 #403278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
403278		abdzag	Inside information (BOI21_servers)	C++17	2.50 / 100	340 ms	63104 KiB

servers

#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)
#define  sz(a) a.size()
typedef long double ld;
using namespace std;
const long long inf = 1e15;
typedef long long ll;
typedef unsigned long long ull;
vector<ll> lis(2e5);
vector<ll> lds(2e5);
vector<ll> ris(2e5);
vector<ll> rds(2e5);
void Uinitate(vector<ll>& p) {
	rep(i, 0, p.size())p[i] = i;
}
ll UfindSet(ll cur, vector<ll>& p) {
	if (p[cur] == cur)return cur;
	return p[cur] = UfindSet(p[cur], p);
}
void Ujoin(ll i, ll j, vector<ll>& p, vector<ll>& r) {
	ll si = UfindSet(i, p);
	ll sj = UfindSet(j, p);
	if (si == sj)return;
	if (r[si] > r[sj])swap(sj, si);
	p[si] = sj;
	r[sj]++;
}
vector<ll> depth(2e5, -1);
pair<pair<ll, ll>, ll> lca(ll a, ll b, vector<vector<pair<ll, ll>>>& parents) {
	bool swaped = depth[a] < depth[b];
	if (depth[a] < depth[b])swap(a, b);
	ll diff = depth[a] - depth[b];
	if (diff % 2 == 0 && diff) {
		a = parents[0][a].first;
		diff--;
	}
	ll mx = 0;
	rrep(i, 19, -1) {
		if (diff & (1 << i)) {
			mx = max(mx, parents[i][a].second);
			if (parents[i][a].first == b) {
				return make_pair(make_pair(a, a), mx);
			}
			a = parents[i][a].first;
		}
	}
	rrep(i, 19, -1) {
		if (parents[i][b] != parents[i][b]) {
			a = parents[i][a].first;
			b = parents[i][b].first;
			mx = max(mx, parents[i][a].second);
			mx = max(mx, parents[i][b].second);
		}
	}
	if (swaped)swap(a, b);
	return make_pair(make_pair(a, b), mx);
}
int main() {
	cin.sync_with_stdio(false);
	ll n, Q;
	cin >> n >> Q;
	vector<vector<pair<ll, ll>>> g(n + 1);
	vector<pair<pair<ll, ll>, pair<ll, ll>>> queries;
	Uinitate(lds);
	Uinitate(lis);
	ll counter = 0;
	rep(i, 0, n + Q - 1) {
		char c;
		ll a, b;
		cin >> c;
		if (c == 'S') {
			cin >> a >> b;
			g[a].emplace_back(b, ++counter);
			g[b].emplace_back(a, counter);
		}
		else if (c == 'Q') {
			cin >> a >> b;
			queries.emplace_back(make_pair(0, counter), make_pair(a, b));
		}
		else {
			cin >> a;
			queries.emplace_back(make_pair(1, counter), make_pair(a, b));
		}
	}

	vector<pair<ll, ll>> parent(n + 1);
	parent[1] = make_pair(1, 0);
	queue<ll> q;
	q.push(1);
	depth[1] = 0;
	while (!q.empty()) {
		ll cur = q.front();
		q.pop();
		rep(i, 0, g[cur].size()) {
			ll v = g[cur][i].first;
			if (depth[v] == -1) {
				depth[v] = depth[cur] + 1;
				q.push(v);
			}
		}
	}
	q.push(1);
	vector<bool> isLeaf(n + 1, 1);
	while (!q.empty()) {
		ll cur = q.front();
		q.pop();
		rep(i, 0, g[cur].size()) {
			if (!parent[g[cur][i].first].first) {
				isLeaf[cur] = false;
				parent[g[cur][i].first] = make_pair(cur, g[cur][i].second);
				q.push(g[cur][i].first);
			}
		}
	}
	queue<pair<ll, ll>> q2;
	rep(i, 1, n + 1)if (isLeaf[i])if (parent[i].first != 1)q2.emplace(parent[i].first, i);
	while (!q2.empty()) {//uses the child node to describe edge
		pair<ll, ll> cur = q2.front();
		q2.pop();
		if (parent[cur.first].second > parent[cur.second].second) {
			Ujoin(cur.first, cur.second, lis, ris);
		}
		if (parent[cur.first].second < parent[cur.second].second) {
			Ujoin(cur.first, cur.second, lds, rds);
		}
		if (parent[cur.first].first != 1)q2.emplace(parent[cur.first].first, cur.first);
	}
	vector<vector<pair<ll, ll>>> parents(20, vector<pair<ll, ll>>(n + 1));
	rep(i, 1, n + 1)parents[0][i] = parent[i];
	rep(i, 1, 20) {
		rep(j, 1, n + 1) {
			parents[i][j].first = parents[i - 1][parents[i - 1][j].first].first;
			parents[i][j].second = max(parents[i - 1][j].second, parents[i - 1][parents[i - 1][j].first].second);
		}
	}
	trav(query, queries) {
		if (query.first.first == 0) {
			ll a = query.second.second;
			ll b = query.second.first;
			pair<pair<ll, ll>, ll> val = lca(a, b, parents); //returns last node before lca for a and b respectively
			if (a == b) {
				cout << "yes" << endl;
				continue;
			}
			if (parent[val.first.first].second <= parent[val.first.second].second) {
				bool anearNode = parent[val.first.first].first == a;
				bool bnearNode = parent[val.first.second].first == b;
				ll mx = max(val.second, max(parent[a].second, parent[b].second));
				if ((UfindSet(a, lis) == UfindSet(val.first.first, lis) || anearNode) && (UfindSet(b, lds) == UfindSet(val.first.second, lds) || bnearNode) && query.first.second >= mx)cout << "yes" << endl;
				else cout << "no" << endl;
			}
			else cout << "no" << endl;
		}
	}
	return 0;
}

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