Submission #441523

#	Time	Username	Problem	Language	Result	Execution time	Memory
441523		8e7	Inside information (BOI21_servers)	C++14	55 / 100	1507 ms	49072 KiB

servers

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
//#include <ext/pb_ds/assoc_contatiner.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) { cout << a << " ";debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << (*l) << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 120005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct query{
	int ti, a, b;
	query() {ti = 0, a = 0, b = 0;}
	query(int x, int y, int z) {ti = x, a = y, b = z;}
};
vector<query> que;
int anc[17][maxn], ma[17][maxn], mi[17][maxn], dep[maxn];
bool inc[17][maxn], decr[17][maxn];

vector<pii> adj[maxn];

void dfs(int n, int par, int d) {
	anc[0][n] = par;
	dep[n] = d;
	inc[0][n] = decr[0][n] = 1;
	for (auto v:adj[n]) {
		if (v.ff != par) {
			ma[0][v.ff] = mi[0][v.ff] = v.ss;
			dfs(v.ff, n, d + 1);
		}
	}
}
pair<int, bool> mono(int a, int b) {
	bool sw = 0, ic = 1, dc = 1;
	int big = 0, small = 1<<20;
	if (dep[a] < dep[b]) sw = 1, swap(a, b);
	int hdif = dep[a] - dep[b], cnt = 0;
	while (hdif) {
		if (hdif & 1) {
			ic &= inc[cnt][a] && ma[0][a] > big;
			dc &= decr[cnt][a] && ma[0][a] < small;	
			big = max(big, ma[cnt][a]), small = min(small, mi[cnt][a]);
			a = anc[cnt][a];
		}
		hdif >>= 1, cnt++;
	}
	return {big, sw ? dc : ic};
}
pair<int, bool> lca(int a, int b) {
	bool sw = 0;
	if (dep[a] < dep[b]) sw = 1, swap(a, b);
	int hdif = dep[a] - dep[b], cnt = 0;
	while (hdif) {
		if (hdif & 1) {
			a = anc[cnt][a];
		}
		hdif >>= 1, cnt++;
	}
	if (a == b) return {a, true};
	for (int i = 16;i >= 0;i--) {
		if (anc[i][a] != anc[i][b]) {
			a = anc[i][a], b = anc[i][b];
		}
	}
	bool val = ma[0][a] < ma[0][b];
	return {anc[0][a], val ^ sw};
}
/*
int cnt = 0, lim = 0;
void solve(int n, int par, int cur) {
	cnt++;
	for (auto v:adj[n]) {
		if (v.ff != par && v.ss > cur && v.ss <= lim) {
			solve(v.ff, n, v.ss);
		}
	}
}
*/
int main() {
	io
	int n, k;
	cin >> n >> k;
	int cur = 1;
	for (int i = 0;i < n + k - 1;i++) {
		char type;
		cin >> type;
		if (type == 'S') {
			int a, b;
			cin >> a >> b;
			adj[a].push_back({b, cur});
			adj[b].push_back({a, cur});
			cur++;
			que.push_back(query(0, a, b));
		} else if (type == 'Q') {
			int a, b;
			cin >> a >> b;
			que.push_back(query(1, b, a));
		} else {
			int d;
			cin >> d;
			que.push_back(query(2, d, 0));
		}
	}
	dfs(1, 0, 1);
	//pary(ma[0] + 1, ma[0] + n + 1);
	for (int i = 1;i < 17;i++) {
		for (int j = 1;j <= n;j++) {
			anc[i][j] = anc[i - 1][anc[i - 1][j]];
			ma[i][j] = max(ma[i - 1][j], ma[i - 1][anc[i - 1][j]]);
			mi[i][j] = min(mi[i - 1][j], mi[i - 1][anc[i - 1][j]]);
			inc[i][j] = inc[i - 1][j] && inc[i - 1][anc[i - 1][j]] && ma[i - 1][j] < ma[0][anc[i - 1][j]];
			decr[i][j] = decr[i - 1][j] && decr[i - 1][anc[i - 1][j]] && mi[i - 1][j] > ma[0][anc[i - 1][j]];
			//debug(i, j, ma[i][j], mi[i][j]);
		}
	}
	cur = 0;
	for (auto i:que) {
		if (i.ti == 1) {
			pii p1 = lca(i.a, i.b);
			//debug(p1.ff, p1.ss);
			pii p2 = mono(i.a, p1.ff), p3 = mono(p1.ff, i.b);
			//debug(p2.ff, p2.ss, p3.ff, p3.ss);
			int big = max(p2.ff, p3.ff);
			bool ans = (big <= cur) && p2.ss && p3.ss && p1.ss;
			cout << (ans ? "yes" : "no") << "\n";	
		} else if (i.ti == 0) {
			cur++;
		} else {
			int ans = 1;
			int low = i.a, up = n + 1;	
			while (low < up - 1) {
				int mid = (low + up) / 2;
				pii p = mono(i.a, mid);
				if (p.ff <= cur && p.ss) low = mid;
				else up = mid;
			}
			ans += low - i.a;
			
			low = 0, up = i.a;
			while (low < up - 1) {
				int mid = (low + up) / 2;
				pii p = mono(i.a, mid);
				if (p.ff <= cur && p.ss) up = mid;
				else low = mid;
			}
			ans += i.a - up;
			cout << ans << "\n";
		}
	}
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6

7 7
S 4 5
S 2 3
S 5 6
S 6 7
S 3 4
S 1 2
C 1
C 2
C 3
C 4
C 5
C 6
C 7
   */

• 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: 5 / 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