제출 #464060

#제출 시각아이디문제언어결과실행 시간메모리
464060AmShZInside information (BOI21_servers)C++17
0 / 100
42 ms24644 KiB
//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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...