#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int N, K, A[120005], B[120005], inc[120005], down[120005], dep[120005], anc[25][120005], wei[25][120005];
char C[120005];
vector<ii> adj[120005];
void dfs(int n, int e = -1, int prv = -1) {
anc[0][n] = e;
wei[0][n] = prv;
for (int k = 1; k < 20; k++)
if (anc[k - 1][n] != -1) {
anc[k][n] = anc[k - 1][anc[k - 1][n]];
wei[k][n] = max(wei[k - 1][n], wei[k - 1][anc[k - 1][n]]);
}
for (auto [u, w] : adj[n]) if (u != e) {
dep[u] = dep[n] + 1;
if (n == 1) inc[u] = down[u] = n;
else if (w < prv) inc[u] = inc[n], down[u] = n;
else down[u] = down[n], inc[u] = n;
dfs(u, n, w);
}
}
bool qry(int u, int v, int t) {
int ou = u, ov = v, m_w = 0;
bool has_swap = 0;
if (dep[u] > dep[v]) {
swap(u, v);
has_swap = 1;
}
for (int k = 19; k >= 0; k--)
if (dep[v] - (1 << k) >= dep[u]) {
m_w = max(m_w, wei[k][v]);
v = anc[k][v];
}
if (u == v) {
if (m_w > t) return 0;
if (dep[ou] <= dep[ov]) return dep[down[ov]] <= dep[ou];
else return dep[inc[ou]] <= dep[ov];
}
if (has_swap) swap(u, v);
for (int k = 19; k >= 0; k--)
if (anc[k][u] != anc[k][v]) {
m_w = max({m_w, wei[k][u], wei[k][v]});
u = anc[k][u];
v = anc[k][v];
}
int lca = anc[0][u];
m_w = max({m_w, wei[0][u], wei[0][v]});
return m_w < t && dep[inc[ou]] <= dep[lca] && dep[down[ov]] <= dep[lca] && wei[0][u] < wei[0][v];
}
main() {
memset(anc, -1, sizeof anc);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for (int i = 1; i <= N + K - 1; i++) {
cin >> C[i];
if (C[i] == 'S' || C[i] == 'Q') cin >> A[i] >> B[i];
else cin >> A[i];
if (C[i] == 'S') {
adj[A[i]].eb(B[i], i);
adj[B[i]].eb(A[i], i);
}
}
inc[1] = down[1] = 1;
dfs(1);
for (int i = 1; i <= N; i++) cout << inc[i] << ' ' << down[i] << '\n';
for (int i = 1; i <= N + K - 1; i++) {
if (C[i] == 'Q') {
if (qry(B[i], A[i], i)) cout << "yes\n";
else cout << "no\n";
} else if (C[i] == 'C') {
}
}
}
Compilation message
servers.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
79 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
29464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
29464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
29496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
29496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
29496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
29496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
29484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
29484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
29516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
29516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
29508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
29508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
