#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19938 rnd(chrono::steady_clock::now().time_since_epoch().count())
#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
struct BIT {
int n;
vector<int> v;
stack<pii> ops;
void init_(int _n) {
n = _n;
v.assign(n + 1, 0);
}
int lowbit(int x) { return x & (-x); }
void modify(int x, int val) {
if(x == 0) return;
if(val > 0) ops.push({x, val});
for(int i = x; i <= n; i += lowbit(i)) {
v[i] += val;
}
}
int query(int x) {
int ans = 0;
for(int i = x; i > 0; i -= lowbit(i)) {
ans += v[i];
}
return ans;
}
int ask(int x) {
return query(n) - query(x - 1);
}
void undo() {
while(ops.size()) {
pii cur = ops.top(); ops.pop();
modify(cur.first, -cur.second);
}
}
};
namespace solver {
int n, k;
BIT bit;
vector<int> vis, mx, sz, R, ch;
vector<int> L, J, es, cost, t, ans, tp;
vector<pii> a;
vector<vector<pii>> nxt;
vector<vector<int>> mp;
void init_(int _n, int _k) {
n = _n, k = _k;
bit.init_(n + k);
vis.assign(n + 1, 0);
mx.assign(n + 1, 0);
sz.assign(n + 1, 0);
R.assign(n + 1, 0);
L.assign(n + 1, 0);
J.assign(n + 1, 0);
es.assign(1, 0);
cost.assign(1, INF);
ch.clear();
tp.assign(k + 1, 0);
a.assign(k + 1, {0, 0});
ans.assign(k + 1, 0);
t.assign(k + 1, 0);
nxt.assign(n + 1, vector<pii>());
mp.assign(n + 1, vector<int>());
}
void add_edge(int a, int b, int c) {
mp[a].push_back(es.size());
mp[b].push_back(es.size());
es.push_back(a ^ b);
cost.push_back(c);
}
void get_sz(int x, int par) {
mx[x] = 0, sz[x] = 1;
ch.push_back(x);
for(auto i : mp[x]) if(i != par) {
int to = es[i] ^ x;
if(vis[to]) continue;
get_sz(to, i);
sz[x] += sz[to];
mx[x] = max(mx[x], sz[to]);
}
}
int get_cen(int x, int par, int tot) {
int best = x;
for(auto i : mp[x]) if(i != par) {
int to = es[i] ^ x;
if(vis[to]) continue;
int cur = get_cen(to, i, tot);
if(max(mx[cur], tot - sz[cur]) <
max(mx[best], tot - sz[best])) best = cur;
}
return best;
}
void dfs(int x, int par, int l, int j, int r) {
J[x] = j, L[x] = l, R[x] = r;
for(auto i : mp[x]) if(i != par) {
int to = es[i] ^ x;
if(vis[to]) continue;
dfs(to, i, l,
(cost[par] > cost[i] ? j : INF),
(cost[par] < cost[i] ? max(cost[i], r) : INF)
);
}
}
void deco(int x, vector<pii> q) {
ch.clear();
get_sz(x, -1);
int c = get_cen(x, -1, sz[x]);
vis[c] = 1;
R[c] = J[c] = L[c] = 0;
vector<vector<pii>> temp(mp[c].size(), vector<pii>());
for(auto i : mp[c]) {
int to = es[i] ^ c;
if(vis[to]) continue;
nxt[i].clear();
dfs(to, i, i, cost[i], cost[i]);
}
vector<pii> s;
for(auto i : q) {
if(i.first == 1) {
int x, y; tie(x, y) = a[i.second];
if(L[x] == L[y]) nxt[L[x]].push_back(i);
else ans[i.second] = (J[y] < cost[L[x]] && t[i.second] > R[x]);
}
else s.push_back({0, i.second});
}
for(auto i : ch) s.push_back({1, i});
sort(all(s), [](pii a, pii b) {
int t1 = (a.first? R[a.second] : t[a.second]);
int t2 = (b.first? R[b.second] : t[b.second]);
return t1 < t2;
});
for(auto i : s) {
if(i.first) bit.modify(min(n + k, cost[L[i.second]]), 1);
else {
int x = a[i.second].first;
ans[i.second] += bit.ask(min(J[x] + 1, n + k + 1));
if(x != c) nxt[L[x]].push_back({2, i.second});
}
}
bit.undo();
rep(i, 0, signed(mp[c].size()) - 1) {
temp[i].swap(nxt[mp[c][i]]);
}
rep(i, 0, signed(mp[c].size()) - 1) {
int e = mp[c][i], to = es[e] ^ c;
if(vis[to]) continue;
deco(to, temp[i]);
}
return;
}
};
using namespace solver;
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n, k, cur = 0;
cin >> n >> k;
init_(n, k);
vector<pii> q;
rep(i, 1, n + k - 1) {
char c; cin >> c;
if(c == 'S') {
int x, y; cin >> x >> y;
add_edge(x, y, i);
}
else if(c == 'Q') {
int x, y; cin >> x >> y;
a[++cur] = {x, y};
tp[cur] = 1, t[cur] = i;
if(x == y) ans[cur] = 1;
else q.push_back({1, cur});
}
else {
int x; cin >> x;
a[++cur] = {x, -1};
tp[cur] = 2, t[cur] = i;
q.push_back({2, cur});
}
}
deco(1, q);
rep(i, 1, k) {
if(tp[i] == 1) cout << (ans[i] ? "yes" : "no") << "\n";
else cout << ans[i] << "\n";
}
return 0;
}
/*
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
*/
Compilation message
servers.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
4 | #pragma loop-opt(on)
|
servers.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
| ^~~~
servers.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
42 ms |
10448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
42 ms |
10448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
43 ms |
9788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
43 ms |
9788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
39 ms |
11492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
39 ms |
11492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
39 ms |
11448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
39 ms |
11448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
40 ms |
11500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
40 ms |
11500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
38 ms |
10396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
38 ms |
10396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
