#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)
#define sz(a) a.size()
typedef long double ld;
using namespace std;
const long long inf = 1e15;
typedef long long ll;
typedef unsigned long long ull;
vector<ll> lis(2e5);
vector<ll> lds(2e5);
vector<ll> ris(2e5);
vector<ll> rds(2e5);
void Uinitate(vector<ll>&p) {
rep(i, 0, p.size())p[i] = i;
}
ll UfindSet(ll cur,vector<ll>&p) {
if (p[cur] == cur)return cur;
return p[cur] = UfindSet(p[cur],p);
}
void Ujoin(ll i, ll j,vector<ll>&p,vector<ll>&r) {
ll si = UfindSet(i,p);
ll sj = UfindSet(j,p);
if (si == sj)return;
if (r[si] > r[sj])swap(sj, si);
p[si] = sj;
r[sj]++;
}
vector<ll> depth(2e5, -1);
pair<pair<ll,ll>,ll> lca(ll a, ll b, vector<vector<pair<ll,ll>>>& parents) {
bool swaped = depth[a] < depth[b];
if (depth[a] < depth[b])swap(a, b);
ll diff = depth[a] - depth[b];
if (diff % 2 == 0 && diff) {
a = parents[0][a].first;
diff--;
}
ll mx = 0;
rrep(i, 19, -1) {
if (diff & (1 << i)) {
mx = max(mx, parents[i][a].second);
if (parents[i][a].first == b) {
return make_pair(make_pair(a, a),mx);
}
a = parents[i][a].first;
}
}
rrep(i, 19, -1) {
if (parents[i][b] != parents[i][b]) {
a = parents[i][a].first;
b = parents[i][b].first;
mx = max(mx, parents[i][a].second);
mx = max(mx, parents[i][b].second);
}
}
if (swaped)swap(a, b);
return make_pair(make_pair(a, b), mx);
}
int main() {
cin.sync_with_stdio(false);
ll n, Q;
cin >> n >> Q;
vector<vector<pair<ll,ll>>> g(n + 1);
vector<pair<pair<ll,ll>, pair<ll,ll>>> queries;
Uinitate(lds);
Uinitate(lis);
ll counter = 0;
rep(i, 0, n + Q - 1) {
char c;
ll a, b;
cin >> c;
if (c == 'S') {
cin >> a >> b;
g[a].emplace_back(b,++counter);
g[b].emplace_back(a,counter);
}
else if (c == 'Q') {
cin >> a >> b;
queries.emplace_back(make_pair(0,counter), make_pair(a, b));
}
else {
cin >> a;
queries.emplace_back(make_pair(1,counter), make_pair(a, b));
}
}
vector<pair<ll, ll>> parent(n + 1);
parent[1] = make_pair(1, 0);
queue<ll> q;
q.push(1);
depth[1] = 0;
while (!q.empty()) {
ll cur = q.front();
q.pop();
rep(i, 0, g[cur].size()) {
ll v = g[cur][i].first;
if (depth[v] == -1) {
depth[v] = depth[cur] + 1;
q.push(v);
}
}
}
q.push(1);
vector<bool> isLeaf(n + 1, 1);
while (!q.empty()) {
ll cur = q.front();
q.pop();
rep(i, 0, g[cur].size()) {
if (!parent[g[cur][i].first].first) {
isLeaf[cur] = false;
parent[g[cur][i].first] = make_pair(cur, g[cur][i].second);
q.push(g[cur][i].first);
}
}
}
queue<pair<ll, ll>> q2;
rep(i, 1, n + 1)if (isLeaf[i])if(parent[i].first != 1)q2.emplace(parent[i].first,i);
while (!q2.empty()) {//uses the child node to describe edge
pair<ll, ll> cur = q2.front();
q2.pop();
if (parent[cur.first].second > parent[cur.second].second) {
Ujoin(cur.first, cur.second, lis, ris);
}
if (parent[cur.first].second < parent[cur.second].second) {
Ujoin(cur.first, cur.second, lds, rds);
}
if (parent[cur.first].first != 1)q2.emplace(parent[cur.first].first,cur.first);
}
vector<vector<pair<ll,ll>>> parents(20,vector<pair<ll,ll>>(n+1));
rep(i, 1, n + 1)parents[0][i] = parent[i];
rep(i, 1, 20) {
rep(j, 1, n + 1) {
parents[i][j].first = parents[i - 1][parents[i - 1][j].first].first;
parents[i][j].second = max(parents[i-1][j].second,parents[i - 1][parents[i - 1][j].first].second);
}
}
trav(query, queries) {
if (query.first.first == 0) {
ll a = query.second.second;
ll b = query.second.first;
pair<pair<ll,ll>,ll> val = lca(a, b,parents); //returns last node before lca for a and b respectively
if (parent[val.first.first].second <= parent[val.first.second].second) {
bool anearNode = parent[val.first.first].first ==a ;
bool bnearNode = parent[val.first.second].first == b;
ll mx = max(val.second, max(parent[a].second, parent[b].second));
if ((UfindSet(a, lis) == UfindSet(val.first.first, lis) || anearNode) && (UfindSet(b, lds) == UfindSet(val.first.second, lds) || bnearNode)&&query.first.second>=mx)cout << "yes" << endl;
else cout << "no" << endl;
}
else cout << "no" << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
225 ms |
12356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
225 ms |
12356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
12408 KB |
Output is correct |
| 2 |
Correct |
318 ms |
65880 KB |
Output is correct |
| 3 |
Correct |
343 ms |
66128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
12408 KB |
Output is correct |
| 2 |
Correct |
318 ms |
65880 KB |
Output is correct |
| 3 |
Correct |
343 ms |
66128 KB |
Output is correct |
| 4 |
Incorrect |
208 ms |
13260 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
226 ms |
12564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
226 ms |
12564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
223 ms |
12324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
223 ms |
12324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
12404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
12404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
233 ms |
12320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
233 ms |
12320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
