| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 403702 | abdzag | Inside information (BOI21_servers) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
vector<ll> depth(2e5, -1);
vector<pair<ll, ll>> parent(2e5);
vector<vector<ll>> parents(20, vector<ll>(2e5));
ll Root = 1;
vector<vector<ll>> children(2e5);
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);
}
void dfs(ll cur, ll last) {
if (cur != Root) {
if (last == Root)lds[cur]=++lis[cur];
else if (parent[cur].second < parent[last].second) {
lis[cur] = lis[last] + 1;
lds[cur] = 1;
}
else {
lds[cur] = lds[last] + 1;
lis[cur] = 1;
}
}
trav(a, children[cur])dfs(a, cur);
}
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;
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));
}
}
parent[Root] = make_pair(Root, 0);
queue<ll> q;
q.push(Root);
depth[Root] = 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(Root);
while (!q.empty()) {
ll cur = q.front();
q.pop();
rep(i, 0, g[cur].size()) {
if (!parent[g[cur][i].first].first) {
parent[g[cur][i].first] = make_pair(cur, g[cur][i].second);
q.push(g[cur][i].first);
children[cur].push_back(g[cur][i].first);
}
}
}
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]];
}
}
dfs(1, 1);
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) {
ll LCA = parent[val.first].first;
//bool aactive = parent[val.first].second <= query.first.second;
//bool bactive = parent[b].second <= query.first.second;
if (depth[a]-lis[a]<=depth[LCA]&&depth[b]-lds[b]<=depth[LCA]&& aactive && bactive)cout << "yes" << endl;
else cout << "no" << endl;
}
else cout << "no" << endl;
}
}
return 0;
}