//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 20;
const int mod = 998244353;
//czy sciezka od a do b uzywa krawedzi ≤t i jest rosnaca??
struct Q{
int a, b, t, idx;
Q(){}
Q(int _a, int _b, int _t, int _idx){
a = _a, b = _b, t = _t, idx = _idx;
}
};
//to be done
struct C{
int v, t, idx;
C(){}
C(int _v, int _t, int _idx){
v = _v, t = _t, idx = _idx;
}
};
struct DSU{
vector<int>rep, sz;
DSU(int n){
rep.resize(n);
iota(rep.begin(), rep.end(), 0);
sz.assign(n, 1);
}
int f(int a){return a == rep[a] ? a : rep[a] = f(rep[a]);}
bool sameset(int a, int b){
return f(a) == f(b);
}
bool u(int a, int b){
a = f(a); b = f(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
rep[b] = a;
return true;
}
};
void solve(){
int n, q; cin >> n >> q;
int m = 1, idx = 1;
vector<Q>Qque;
vector<C>Cque;
vector<int>ans(q+1);
vector<vector<T>>g(n+1);
vector<T>edges = {{0, 0}};
for (int i = 1; i<n+q; i++){
char c; cin >> c;
if (c == 'S'){
int a, b; cin >> a >> b;
g[a].emplace_back(b, m);
g[b].emplace_back(a, m);
edges.emplace_back(a, b);
m++;
} else if (c == 'Q'){
int a, b; cin >> a >> b;
Qque.emplace_back(a, b, m, idx++);
} else {
int a; cin >> a;
Cque.emplace_back(a, m, idx++);
}
}
DSU dsu(n+2);
vector up(n+1, vector<int>(K));
vector mn(n+1, vector<int>(K, oo));
vector<int>depth(n+1);
vector<int>cost(n+1);
function<void(int, int, int)>dfs = [&](int v, int pa, int c){
up[v][0] = pa;
cost[v] = c;
for (int i = 1; i<K; i++) {
up[v][i] = up[up[v][i-1]][i-1];
if (i > 1) mn[v][i] = min(mn[v][i-1], mn[up[v][i-1]][i-1]);
}
for (auto [x, id]: g[v]){
if (x == pa) continue;
depth[x] = depth[v]+1;
mn[x][1] = id - c;
dfs(x, v, id);
}
};
dfs(1, 1, -oo);
auto lca = [&](int a, int b){
if (depth[a] > depth[b]) swap(a, b);
for (int i = K-1; i>=0; i--){
if (depth[b] - (1<<i) >= depth[a]){
b = up[b][i];
}
}
if (a == b) return a;
for (int i = K-1; i>=0; i--){
if (up[a][i] != up[b][i]){
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
};
int ptr = 0;
auto is_increasing = [&](int a, int b){
//sciezka pionowa od a do b (b w poddrzewie a)
if (depth[b] - depth[a] <= 1) return true;
int jump = depth[b] - depth[a] - 2;
int currmn = oo, v = b;
for (int i = K-1; i>=1; i--){
if (jump&(1<<i)){
currmn = min(currmn, mn[v][i]);
v = up[v][i];
}
}
return (currmn > 0);
};
debug(edges);
auto below_lca = [&](int a, int b){
bool f = 0;
if (depth[a] < depth[b]) {
swap(a, b);
f = 1;
}
for (int i = K-1; i>=0; i--){
if (depth[a] - (1<<i) >= depth[b]){
a = up[a][i];
}
}
assert(a != b);
for (int i = K-1; i>=0; i--){
if (up[a][i] != up[b][i]){
a = up[a][i];
b = up[b][i];
}
}
if (f) swap(a, b);
return T{a, b};
};
for (auto [a, b, t, id]: Qque){
while (ptr + 1 < t){
ptr++;
dsu.u(edges[ptr].first, edges[ptr].second);
}
if (!dsu.sameset(a, b)) {
cout << "no\n";
continue;
}
int l = lca(a, b);
debug(a, b, l);
if (l == b){
//sciezka ma byc rosnaca
if (is_increasing(b, a)) cout << "yes\n";
else cout << "no\n";
continue;
}
if (l == a){
//sciezka ma byc malejaca
if (!is_increasing(a, b)) cout << "yes\n";
else cout << "no\n";
continue;
}
//rosnaca od a do l i malejaca od l do b
T now = below_lca(a, b);
if (is_increasing(l, a) && !is_increasing(l, b) && cost[now.first] < cost[now.second]) cout << "yes\n";
else cout << "no\n";
}
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
5500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
5500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
