# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
666705 | MilosMilutinovic | Inside information (BOI21_servers) | C++14 | 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.
#inlude <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<pair<int, int>> g(n);
vector<char> op(q);
vector<int> x(q);
vector<int> y(q);
for (int i = 0; i < q; i++) {
cin >> op[i];
if (op[i] == 'S') {
cin >> x[i] >> y[i];
--x[i]; --y[i];
g[x[i]].emplace_back(y[i], i);
g[y[i]].emplace_back(x[i], i);
}
if (op[i] == 'Q') {
cin >> x[i] >> y[i];
--x[i]; --y[i];
}
if (op[i] == 'C') {
cin >> x[i];
--x[i];
}
}
vector<int> qs(n);
for (int i = 0; i < q; i++) {
qs[x[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
sort(g[i].begin(), g[i].end(), [&](pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
});
}
vector<bool> was(n);
vector<int> sz(n);
function<void(int, int)> Find_sz = [&](int v, int pv) {
sz[v] = 1;
for (auto& p : g[v]) {
int to = p.first;
if (!was[to] && to != pv) {
Find_sz(to, v);
sz[v] += sz[to];
}
}
};
function<int(int, int, int)> Find_cen = [&](int v, int pv, int n) {
for (auto& p : g[v]) {
int to = p.first;
if (!was[to] && to != pv && sz[to] * 2 >= n) {
return Find_cen(to, v, n);
}
}
return v;
};
vector<int> qv;
function<void(int, int, int, bool, bool)> Go = [&](int v, int pv, int prv_w, int fir, bool inc, bool dec) {
if (dec) {
for (auto& p : qs[v]) {
ans[p] += Query(i) + (fir <= p);
}
}
if (inc) {
qv.push_back(prv_w);
}
for (auto& p : g[v]) {
int to = p.first;
int w = p.second;
if (!was[to] && to != pv) {
Go(to, v, w, fir, (inc & (w > prv_w)), (dec & (w < prv_w)));
}
}
};
function<void(int, int)> Decompose = [&](int v, int pv) {
Find_sz(v, v);
v = Find_cen(v, v);
was[v] = true;
vector<int> rv;
for (auto& p : g[v]) {
int to = p.first;
int w = p.second;
if (!was[to]) {
Go(to, v, w, w, 1, 1);
for (auto& p : qv) {
Modify(p, +1);
rv.push_back(p);
}
}
}
for (auto& p : qs[v]) {
ans[p] += Query(p);
}
for (auto& p : rv) {
Modify(p, -1);
}
};
Decompose(0, 0);
return 0;
}
// todo