제출 #464060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464060		AmShZ	Inside information (BOI21_servers)	C++17	0 / 100	42 ms	24644 KiB

servers

//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 3e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 1e9 + 7;//998244353;
const int base = 257;

int n, k, sz[xn], ans[xn], fen[xn], a[xn], qt[xn];
vector <int> QG[xn], vec, V;
vector <pii> adj[xn], Q[xn];
bool hide[xn], mark[xn], fl[2][xn];

void plant(int v, int p = - 1){
	sz[v] = 1;
	for (pii u : adj[v])
		if (!hide[u.A] && u.A != p)
			plant(u.A, v), sz[v] += sz[u.A];
}
int find_centroid(int v, int s, int p = - 1){
	for (pii u : adj[v])
		if (!hide[u.A] && u.A != p && s < sz[u.A] * 2)
			return find_centroid(u.A, s, v);
	return v;
}
bool cmp(pii x, pii y){
	return y.B < x.B;
}
void DFS(int v, int p = - 1){
	fl[0][v] = fl[0][p];
	if (!hide[p])
		fl[0][v] &= (a[v] < a[p]);
	fl[1][v] = fl[1][p];
	if (!hide[p])
		fl[1][v] &= (a[p] < a[v]);
	vec.push_back(v);
	for (pii u : adj[v])
		if (!hide[u.A] && u.A != p)
			a[u.A] = u.B, DFS(u.A, v);
}
void mofen(int pos, int val){
	for (pos += 5; pos < xn; pos += pos & - pos)
		fen[pos] += val;
}
int gefen(int pos){
	int res = 0;
	for (pos += 5; 0 < pos; pos -= pos & - pos)
		res += fen[pos];
	return res;
}
void solve(int v){
	plant(v);
	v = find_centroid(v, sz[v]);
	hide[v] = true;
	sort(all(adj[v]), cmp);
	a[v] = 0, mofen(0, 1);
	mark[v] = true, V.clear();
	V.push_back(v);
	fl[0][v] = fl[1][v] = true;
	for (pii u : adj[v]){
		if (hide[u.A])
			continue;
		vec.clear();
		a[u.A] = u.B, DFS(u.A, v);
		for (int x : vec){
			V.push_back(x);
			for (pii y : Q[x])
				if (mark[y.A])
					ans[y.B] = (fl[1][y.A] && fl[0][x] && a[y.A] <= y.B);
			for (int y : QG[x])
				if (fl[0][x])
					ans[y] += gefen(y);
		}
		for (int x : vec)
			if (fl[1][x])
				mofen(a[x], 1), mark[x] = true;
	}
	for (pii y : Q[v])
		if (mark[y.A])
			ans[y.B] = (fl[1][y.A] && a[y.A] <= y.B);
	for (int y : QG[v])
		ans[y] += gefen(y);
	for (int x : V)
		if (fl[1][x])
			mofen(a[x], - 1), mark[x] = false;
	for (pii u : adj[v])
		if (!hide[u.A])
			solve(u.A);
}

int main(){
	fast_io;

	cin >> n >> k;
	for (int i = 1; i < n + k; ++ i){
		char c;
		int x, y;
		cin >> c;
		if (c == 'S'){
			cin >> x >> y;
			adj[x].push_back({y, i});
			adj[y].push_back({x, i});
		}
		else if (c == 'Q'){
			cin >> x >> y;
			Q[y].push_back({x, i});
			qt[i] = 1;
		}
		else{
			cin >> x;
			QG[x].push_back(i);
			qt[i] = 2;
		}
	}
	solve(1);
	for (int i = 1; i < n + k; ++ i){
		if (qt[i] == 2)
			cout << ans[i] << endl;
		else if (qt[i] == 1){
			if (ans[i])
				cout << "yes\n";
			else
				cout << "no\n";
		}
	}

	return 0;
}
/*
6 13
C 1
S 1 2
C 1
S 1 3
C 1
S 3 4
C 1
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

*/

• 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