#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &pr) {out << "(" << pr.first << "; " << pr.second << ")";return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &s) {out << "{";for(const auto &x : s)out << x << ", ";out << "}";return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &m) {out << "{";for(const auto &x : m)out << x << ", ";out << "}";return out;}
template<class T>
ostream& operator<<(ostream& out, const vector<T> &a){out << "[";for(const auto &x : a)out << x << ", ";out << "]";return out;}
#define dmp(x) cerr << #x << " = " << x << endl
#define dmpn(x) cerr << #x << " = " << x << "; "
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define contains(s,x) ((s).find(x) != (s).end())
const int MOD = 998244353;
struct DSU {
int N;
vector<int> parents, heights;
DSU(int n) {
N = n;
parents.assign(N, -1);
heights.assign(N, 1);
}
int find_set(int u) {
if (parents[u] == -1) return u;
return find_set(parents[u]);
}
void unite(int u, int v) {
u = find_set(u);
v = find_set(v);
if (u == v) return;
if (heights[u] < heights[v]) swap(u, v);
if (heights[u] == heights[v]) heights[u]++;
parents[v] = u;
}
};
struct Query {
int u, v, idx;
};
struct Up {
int u = 0, first_edge = 0, last_edge = 0;
bool incr = true, decr = true;
};
int N, K, LOG = 3;
vector<vector<pii>> adj;
vector<vector<Up>> ups;
vector<int> answers, parents, intimes, outtimes;
void preprocess_dfs(int u, int p, int &time, int prev_edge_id = 0) {
intimes[u] = time++;
parents[u] = p;
ups[u][0] = { p, prev_edge_id, prev_edge_id, true, true };
for (int i = 1; i < LOG; i++) {
Up prev = ups[u][i - 1];
Up next = ups[prev.u][i - 1];
bool incr = prev.last_edge < next.first_edge;
ups[u][i] = {
next.u,
prev.first_edge,
next.last_edge,
(prev.incr && next.incr && (incr || next.first_edge == 0)),
(prev.decr && next.decr && (!incr || next.first_edge == 0))
};
// dmpn(u); dmpn(next.u); dmpn(ups[u][i].incr); dmp(ups[u][i].decr);
}
for (auto [id, v] : adj[u]) {
if (v != p) {
preprocess_dfs(v, u, time, id);
}
}
outtimes[u] = time++;
}
// Whether u is ancestor of v.
bool is_ancestor(int u, int v) {
return (intimes[u] <= intimes[v] && outtimes[u] >= outtimes[v]);
}
int lca(int u, int v) {
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = LOG - 1; i >= 0; i--) {
int next = ups[u][i].u;
if (!is_ancestor(next, v)) u = next;
}
return parents[u];
}
bool path_increasing(int u, int v) {
int lanc = lca(u, v);
bool incr = true;
for (int i = LOG - 1, x = u; i >= 0; i--) {
Up next = ups[x][i];
if (!is_ancestor(next.u, v) || next.u == lanc) {
x = next.u;
if (!next.incr) incr = false;
}
}
bool decr = true;
for (int i = LOG - 1, x = v; i >= 0; i--) {
Up next = ups[x][i];
if (!is_ancestor(next.u, u) || next.u == lanc) {
x = next.u;
if (!next.decr) decr = false;
}
}
return incr && decr;
}
int bruteforce_dfs(int u, int p, int target, int prev_edge_id = 0) {
int cnt = (target == -1 || u == target);
for (auto [id, v] : adj[u]) {
if (v != p && id > prev_edge_id) {
cnt += bruteforce_dfs(v, u, target, id);
}
}
return cnt;
}
void solve() {
cin >> N >> K;
adj.assign(N, {});
ups.assign(N, vector<Up>(LOG, Up{}));
answers.assign(K, -3);
intimes.assign(N, -1);
outtimes.assign(N, -1);
parents.assign(N, -1);
DSU dsu(N);
int Q = N - 1 + K, query_idx = 0, edge_idx = 1;
vector<Query> queries;
while (Q--) {
char type;
int u;
cin >> type >> u;
u--;
if (type == 'S') {
int v;
cin >> v;
v--;
adj[u].pb({ edge_idx, v });
adj[v].pb({ edge_idx, u });
dsu.unite(u, v);
edge_idx++;
} else if (type == 'Q') {
int v;
cin >> v;
v--;
if (dsu.find_set(u) != dsu.find_set(v)) {
answers[query_idx] = -2;
} else {
queries.pb({ u, v, query_idx });
}
query_idx++;
} else {
answers[query_idx] = bruteforce_dfs(u, -1, -1);
query_idx++;
}
}
int time = 0;
preprocess_dfs(0, 0, time);
for (Query q : queries) {
if (path_increasing(q.v, q.u)) answers[q.idx] = -1;
else answers[q.idx] = -2;
}
for (int x : answers) {
if (x == -1) cout << "yes" << endl;
else if (x == -2) cout << "no" << endl;
else cout << x << endl;
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
1628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
1628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
1992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
1992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
1672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
1672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
140 ms |
1696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
140 ms |
1696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
1632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
1632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
1732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
1732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
