#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 Edge {
int parent = 0, child = 0, id = 0;
};
struct Query {
int u, edge_id, idx;
};
struct Up {
int u = 0, first_edge = 0, last_edge = 0;
bool incr = true, decr = true;
};
int N, K, LOG = 3;
vector<vector<Edge>> adj;
vector<Edge> edges;
vector<vector<Up>> ups;
vector<int> answers, intimes, outtimes;
void preprocess_dfs(int u, int p, int &time) {
intimes[u] = time++;
int parent_edge = 0;
for (Edge &e : adj[u]) {
if ((e.child == p && e.parent == u) || (e.parent != p && e.child == u)) {
swap(e.child, e.parent);
}
if (e.parent == p && e.child == u) parent_edge = e.id;
}
ups[u][0] = { p, parent_edge, parent_edge, 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 (Edge e : adj[u]) {
if (e.parent == u) {
preprocess_dfs(e.child, u, time);
}
}
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;
}
for (Edge e : adj[u]) if (e.child == u) return e.parent;
return 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;
}
void solve() {
cin >> N >> K;
adj.assign(N, {});
edges.assign(N, {});
answers.assign(K, -3);
intimes.assign(N, -1);
outtimes.assign(N, -1);
ups.assign(N, vector<Up>(LOG, Up{}));
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--;
Edge e = { u, v, edge_idx };
edges[edge_idx] = e;
adj[u].pb(e);
adj[v].pb(e);
dsu.unite(u, v);
edge_idx++;
} else if (type == 'Q') {
int edge_id;
cin >> edge_id;
int v = edges[edge_id].parent;
if (dsu.find_set(u) != dsu.find_set(v)) {
answers[query_idx] = -2;
} else {
queries.pb({ u, edge_id, query_idx });
}
query_idx++;
} else {
answers[query_idx] = -4;
query_idx++;
}
}
int time = 0;
preprocess_dfs(0, 0, time);
for (Query q : queries) {
if (path_increasing(q.edge_id - 1, 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 |
146 ms |
2696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
146 ms |
2696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
3280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
3280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
2656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
2656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
2380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
2380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
