#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define CHECK_BIT(var, pos) ((var) & (1 << (pos)))
using namespace std;
typedef pair<int, int> pi;
const int MAXUP = 19;
const int INF = 1e9;
struct State {
int node;
int ancestor;
bool up;
bool down;
int time_mn;
int time_mx;
State(int n, int p, bool u, bool d, int tn, int tx) : node(n), ancestor(p), up(u), down(d), time_mn(tn), time_mx(tx) {}
State() {}
};
// It must hold that a.ancestor == b.node
State merge(State a, State b) {
State c;
if (a.time_mn == -1) {
return b;
}
c.node = a.node;
c.ancestor = b.ancestor;
c.time_mn = min(a.time_mn, b.time_mn);
c.time_mx = max(a.time_mx, b.time_mx);
c.up = (a.up && b.up) && (a.time_mx <= b.time_mn);
c.down = (a.down && b.down) && (b.time_mx <= a.time_mn);
return c;
}
int N, K;
vector<int> dep;
vector<vector<pi>> adj_list;
vector<vector<State>> ancestor;
vector<vector<int>> queries;
void dfs(int node, int par) {
for (auto [neigh, t] : adj_list[node]) {
if (neigh == par) {
dep[node] = dep[par] + 1;
ancestor[0][node] = State(node, par, true, true, t, t);
continue;
}
dfs(neigh, node);
}
}
void precalculate(void) {
for (int up = 1; up < MAXUP; up++) {
for (int i = 0; i < N; i++) {
ancestor[up][i] = merge(ancestor[up - 1][i], ancestor[up - 1][ancestor[up - 1][i].ancestor]);
}
}
}
State jump(State a, int w) {
for (int up = MAXUP - 1; up >= 0; up--) {
if (CHECK_BIT(w, up)) {
a = merge(a, ancestor[up][a.ancestor]);
}
}
return a;
}
pair<bool, int> lca(int u, int v) {
State a = State(u, u, true, true, -1, -1);
State b = State(v, v, true, true, -1, -1);
if (dep[u] > dep[v]) {
a = jump(a, dep[u] - dep[v]);
if (a.ancestor == b.ancestor) {
return mp(a.up, a.time_mx);
}
}
else {
b = jump(b, dep[v] - dep[u]);
if (a.ancestor == b.ancestor) {
return mp(b.down, b.time_mx);
}
}
for (int up = MAXUP - 1; up >= 0; up--) {
State t_a = merge(a, ancestor[up][a.ancestor]);
State t_b = merge(b, ancestor[up][b.ancestor]);
if (t_a.ancestor != t_b.ancestor) {
a = t_a;
b = t_b;
}
}
a = merge(a, ancestor[0][a.ancestor]);
b = merge(b, ancestor[0][b.ancestor]);
bool good = a.up && b.down && (a.time_mx < b.time_mn);
return mp(good, b.time_mx);
}
int main(void) {
scanf("%d %d", &N, &K);
adj_list.resize(N);
ancestor.resize(MAXUP, vector<State>(N));
dep.resize(N);
for (int t = 0; t < K + N - 1; t++) {
char c;
scanf(" %c", &c);
if (c == 'S') {
int u, v;
scanf("%d %d", &u, &v);
u--; v--;
adj_list[u].pb(mp(v, t));
adj_list[v].pb(mp(u, t));
}
else if (c == 'Q') {
int u, v;
scanf("%d %d", &u, &v);
u--; v--;
queries.pb({u, v, t});
}
else {
int c;
scanf("%d", &c);
}
}
ancestor[0][0] = State();
dfs(0, 0);
precalculate();
for (auto q : queries) {
int u = q[0];
int v = q[1];
int t = q[2];
pair<bool, int> res = lca(v, u);
if (res.first && res.second < t) {
printf("yes\n");
}
else {
printf("no\n");
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
servers.cpp: In function 'int main()':
servers.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d %d", &N, &K);
| ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
servers.cpp:129:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:137:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:143:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | scanf("%d", &c);
| ~~~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |