#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<vector<pair<int, int>>> g(n);
int q = n - 1 + k;
vector<char> foo(q);
vector<int> x(q);
vector<int> y(q);
for (int i = 0; i < q; i++) {
cin >> foo[i] >> x[i] >> y[i];
--x[i], --y[i];
assert(x[i] >= 0 && x[i] < n && y[i] >= 0 && y[i] < n);
if (foo[i] == 'S') {
g[x[i]].emplace_back(y[i], i);
g[y[i]].emplace_back(x[i], i);
}
}
vector<int> par(n);
vector<int> wei(n);
vector<int> dep(n);
function<void(int, int)> Dfs = [&](int u, int pr) {
dep[u] = dep[pr] + 1;
for (auto& e : g[u]) {
int v = e.first;
int w = e.second;
if (v == pr) {
continue;
}
par[v] = u;
wei[v] = w;
Dfs(v, u);
}
};
Dfs(0, 0);
wei[0] = 1000000;
const int L = 20;
vector<vector<int>> up(n, vector<int>(L));
for (int i = 0; i < n; i++) {
up[i][0] = par[i];
}
for (int j = 1; j < L; j++) {
for (int i = 0; i < n; i++) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
auto Lca = [&](int u, int v) {
if (dep[u] < dep[v]) {
swap(u, v);
}
for (int i = L - 1; i >= 0; i--) {
if (dep[up[u][i]] >= dep[v]) {
u = up[u][i];
}
}
if (u == v) {
return u;
}
for (int i = L - 1; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
};
auto Lift = [&](int x, int d) {
for (int i = L - 1; i >= 0; i--) {
if (d >> i & 1) {
x = up[x][i];
}
}
return x;
};
vector<vector<int>> go(n, vector<int>(2, 0));
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return dep[i] < dep[j];
});
for (int id = 1; id < n; id++) {
int i = order[id];
if (wei[par[i]] > wei[i]) {
go[i][0] = go[par[i]][0];
go[i][1] = par[i];
} else {
go[i][0] = par[i];
go[i][1] = go[par[i]][1];
}
}
for (int i = 0; i < q; i++) {
if (foo[i] != 'Q') {
continue;
}
if (x[i] == y[i]) {
cout << "yes" << '\n';
continue;
}
int z = Lca(x[i], y[i]);
bool ok = true;
if (x[i] != z && y[i] != z) {
int p_x = Lift(x[i], dep[x[i]] - dep[z] - 1);
int p_y = Lift(y[i], dep[y[i]] - dep[z] - 1);
if (wei[p_y] > wei[p_x]) {
ok = false;
}
}
if (x[i] != z && wei[x[i]] > i) {
ok = false;
}
if (y[i] != z && wei[Lift(y[i], dep[y[i]] - dep[z] - 1)] > i) {
ok = false;
}
if (dep[go[y[i]][0]] <= dep[z] && dep[go[x[i]][1]] <= dep[z] && ok) {
cout << "yes" << '\n';
} else {
cout << "no" << '\n';
}
}
return 0;
}
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:6:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
6 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:7:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
516 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
516 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
