#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "
const ll mod = 1e9 + 7;
const int maxn = 2e5 + 5e4 + 4;
const int INF = 1e9;
struct Node {
int fi, se;
bool operator < (const Node &other) const {
return se > other.se;
}
};
struct seg_tree {
vector<int> t;
seg_tree() {
t.resize(4 * maxn);
}
void update(int pos, int val, int v = 1, int l = 1, int r = maxn - 1) {
if (l == r) {
t[v] += val;
return;
}
int m = (l + r) / 2;
if (pos <= m) update(pos, val, 2 * v, l, m);
else update(pos, val, 2 * v + 1, m + 1, r);
}
int get(int r, int l = 1, int v = 1, int tl = 1, int tr = maxn - 1) {
if (tl > r || tr < l) return 0;
if (tl >= l && tr <= r) return t[v];
int m = (tl + tr) / 2;
int L = get(r, l, 2 * v, tl, m);
int R = get(r, l, 2 * v + 1, m + 1, r);
return L + R;
}
} IT;
int cnt = 0;
int n, k, res[maxn];
set<Node> adj[maxn];
vector<int> query_c[maxn], cur;
set<pair<int,int>> query_q[maxn];
map<int,int> L;
stack<pair<int,int>> rev;
void dfs_in(int u, int p, int pre) {
auto it = query_q[u].begin();
while (it != query_q[u].end()) {
auto idx = L.find(it->fi);
if (idx == L.end() || idx->se > it->se)
continue;
res[it->se] = -1;
it = query_q[u].erase(it);
}
cur.push_back(u);
for (auto it : adj[u]) {
int v = it.fi, w = it.se;
if (w < pre && v != p)
dfs_in(v, u, w);
}
}
void dfs_out(int u, int p, int pre) {
L[u] = pre;
IT.update(pre, 1);
rev.push({pre, 1});
for (auto it : adj[u]) {
int v = it.fi, w = it.se;
if (w > pre && v != p)
dfs_out(v, u, w);
}
}
void Solve(int u) {
L.clear();
for (auto it : adj[u]) {
cur.clear();
int v = it.fi, w = it.se;
L[u] = w;
dfs_in(v, u, w);
for (auto i : cur) {
for (auto it : query_c[i]) if (it > w)
res[it] += IT.get(it) + 1;
}
dfs_out(v, u, w);
}
auto it = query_q[u].begin();
while (it != query_q[u].end()) {
auto idx = L.find(it->fi);
if (idx == L.end() || idx->se > it->se) {
it++;
continue;
}
res[it->se] = -1;
it = query_q[u].erase(it);
}
for (auto it : query_c[u]) {
cnt++;
res[it] += IT.get(it) + 1;
}
while (!rev.empty()) {
int u, i; tie(u, i) = rev.top(); rev.pop();
IT.update(u, -i);
}
}
struct Centroid_Decomposition {
int sz[maxn];
int dfs(int u, int p) {
sz[u] = 1;
for (auto it : adj[u])
if (it.fi != p)
sz[u] += dfs(it.fi, u);
return sz[u];
}
int Centroid(int u, int p, int tot) {
for (auto it : adj[u])
if (it.fi != p && sz[it.fi] > tot / 2)
return Centroid(it.fi, u, tot);
return u;
}
void build(int u) {
int tot = dfs(u, 0);
int c = Centroid(u, 0, tot);
Solve(c);
vector<Node> del(adj[c].begin(), adj[c].end());
for (auto it : del) {
adj[c].erase(it);
adj[it.fi].erase(adj[it.fi].find({c, it.se}));
build(it.fi);
}
}
} Cen;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen(".INP", "r", stdin);
//freopen(".OUT", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n + k - 1; i++)
res[i] = -3;
for (int i = 1; i <= n + k - 1; i++) {
char type; int u; cin >> type >> u;
if (type == 'S') {
int v; cin >> v;
adj[u].insert({v, i});
adj[v].insert({u, i});
}
else if (type == 'Q') {
int v; cin >> v;
if (u == v) res[i] = -1;
else {
query_q[v].insert({u, i});
res[i] = -2;
}
}
else {
query_c[u].pb(i);
res[i] = 0;
}
}
Cen.build(1);
for (int i = 1; i <= n + k - 1; i++)
if (res[i] != -3) {
if (res[i] >= 0) cout << res[i];
else cout << (res[i] == -1 ? "yes" : "no");
cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3579 ms |
39680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3579 ms |
39680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3564 ms |
39652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3564 ms |
39652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3548 ms |
39640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3548 ms |
39640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3594 ms |
39692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3594 ms |
39692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3598 ms |
39628 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3598 ms |
39628 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3567 ms |
39592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3567 ms |
39592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
