/*
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
\\ //
// 271828___182845__904523__53602__ \\
\\ 87___47____13______52____66__24_ //
// 97___75____72______47____09___36 \\
\\ 999595_____74______96____69___67 //
// 62___77____24______07____66__30_ \\
\\ 35___35____47______59____45713__ //
// \\
\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_map>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7, inf = 1e12;
int n, k, timer = 0;
vector<vector<pair<int, int>>> gp;
vector<vector<int>> up;
vector<int> achox, nvazox, d, tin, tout, par;
void dfs(int u, int p, int h, int lst) {
up[u][0] = p;
par[u] = p;
tin[u] = ++timer;
for (int i = 1; i < 20; ++i) up[u][i] = up[up[u][i - 1]][i - 1];
achox[u] = h;
for (pair<int, int>& v : gp[u]) {
if (v.first != p) {
d[v.first] = d[u] + 1;
if (v.second >= lst) dfs(v.first, u, h, v.second);
else dfs(v.first, u, u, v.second);
}
}
tout[u] = ++timer;
}
void dfs1(int u, int p, int h, int lst) {
nvazox[u] = h;
for (pair<int, int>& v : gp[u]) {
if (v.first != p) {
if (v.second <= lst) dfs1(v.first, u, h, v.second);
else dfs1(v.first, u, u, v.second);
}
}
}
bool isAncestor(int u, int v) {
return tin[u] > tin[v] && tout[u] < tout[v];
}
int lca(int u, int v) {
if (isAncestor(u, v)) return v;
if (isAncestor(v, u))return u;
for (int i = 19; i >= 0; --i) {
if (!isAncestor(v, up[u][i])) u = up[u][i];
}
return up[u][0];
}
void solve() {
cin >> n >> k;
vector<pair<pair<int, int>, int>> query;
gp = vector<vector<pair<int, int>>>(n);
vector<vector<int>> upd(n);
up = vector<vector<int>>(n, vector<int>(20));
nvazox = tin = tout = par = d = achox = vector<int>(n);
vector<pair<pair<int, int>, int>> edg;
map<pair<int, int>, int> mp;
for (int i = 0; i < n + k - 1; ++i) {
char c; cin >> c;
if (c == 'S') {
int u, v; cin >> u >> v;
gp[--u].push_back({ --v, i + 1 });
gp[v].push_back({ u, i + 1 });
mp[{u, v}] = mp[{v, u}] = i + 1;
//ws[{u, v }] = 1;
}
else {
int a, d; cin >> a >> d;
query.push_back({ {--a, --d}, i + 1 });
}
}
dfs(0, 0, 0, 0);
dfs1(0, 0, 0, 1e9);
for (pair<pair<int, int>, int> x : query) {
int A = x.first.first, D = x.first.second, w = x.second;
int l = lca(A, D);
/*int wa = 0, wd = 0;
for (pair<int, int>& v : gp[l]) {
if (v.first == par[l]) continue;
if (tin[A] >= tin[v.first] && tout[A] <= tout[v.first]) wa = v.second;
if (tin[D] >= tin[v.first] && tout[D] <= tout[v.first]) wd = v.second;
}
if (d[achox[A]] <= d[l] && d[nvazox[D]] <= d[l] && wa >= wd) cout << "yes\n";
else cout << "no\n";*/
if (A == D) cout << "yes\n";
else if (d[achox[A]] > d[l] || d[nvazox[D]] > d[l]) cout << "no\n";
else if (tin[D] < tin[A] && tout[D] > tout[A] && mp[{A, par[A]}] <= w) cout << "yes\n";
else if (tin[A] < tin[D] && tout[D] < tout[A]) cout << "no\n";
else if (max(mp[{par[A], A}], mp[{par[D], D}]) > w) cout << "no\n";
else if (mp[{par[A], A}] > mp[{par[D], D}]) cout << "yes\n";
else cout << "no\n";
}
}
/*
TEST
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
Q 1 5
Q 1 5
Q 1 5
Q 1 5
Q 1 5
Q 1 5
*/
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
//int _; cin >> _; while (_--)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
2368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
2368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
2376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
2376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
2360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
2360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
2408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
2408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
