#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<ll, ll> lca(ll a, ll b, vector<vector<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];
diff--;
}
ll mx = 0;
rrep(i, 19, -1) {
if (diff & (1 << i)) {
if (parents[i][a] == b) {
return make_pair(a,a);
}
a = parents[i][a];
}
}
rrep(i, 19, -1) {
if (parents[i][b] != parents[i][b]) {
a = parents[i][a];
b = parents[i][b];
}
}
if (swaped)swap(a, b);
return make_pair(a,b);
}
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<ll>> parents(20, vector<ll>(n + 1));
rep(i, 1, n + 1)parents[0][i] = parent[i].first;
rep(i, 1, 20) {
rep(j, 1, n + 1) {
parents[i][j] = parents[i - 1][parents[i - 1][j]];
}
}
trav(query, queries) {
if (query.first.first == 0) {
ll a = query.second.second;//want to know whether chunk of data a is in server b
ll b = query.second.first;
pair<ll, ll> val = lca(a, b, parents); //returns last node before lca for a and b respectively
if (a == b) {
cout << "yes" << endl;
continue;
}
if (parent[val.first].second <= parent[val.second].second) {
bool anearNode = parent[val.first].first == a|| parent[a].first == val.first;
bool bnearNode = parent[val.second].first == b||parent[b].first==val.second;
bool aactive = parent[val.first].second <= query.first.second;
bool bactive= parent[b].second <= query.first.second;
if ((UfindSet(a, lis) == UfindSet(val.first, lis) || anearNode) && (UfindSet(b, lds) == UfindSet(val.second, lds) || bnearNode) && aactive &&bactive)cout << "yes" << endl;
else cout << "no" << endl;
}
else cout << "no" << endl;
}
}
return 0;
}
Compilation message
servers.cpp: In function 'std::pair<long long int, long long int> lca(ll, ll, std::vector<std::vector<long long int> >&)':
servers.cpp:41:5: warning: unused variable 'mx' [-Wunused-variable]
41 | ll mx = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
12356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
12356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
12360 KB |
Output is correct |
| 2 |
Correct |
312 ms |
43924 KB |
Output is correct |
| 3 |
Correct |
377 ms |
43764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
12360 KB |
Output is correct |
| 2 |
Correct |
312 ms |
43924 KB |
Output is correct |
| 3 |
Correct |
377 ms |
43764 KB |
Output is correct |
| 4 |
Incorrect |
212 ms |
12852 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
231 ms |
12388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
231 ms |
12388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
12316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
12316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
255 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
255 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
223 ms |
12392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
223 ms |
12392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
