| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 739064 | tch1cherin | 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.
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops","omit-frame-pointer","inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
struct CustomHash {
uint64_t operator()(size_t x) {
static uint64_t RANDOM = chrono::steady_clock().now().time_since_epoch().count();
return x ^ RANDOM;
}
};
struct fenwick {
int size;
vector<int> fenw, changes;
fenwick() {}
fenwick(int _size) : size(_size), fenw(_size + 1) {}
void add(int i, int v) {
for (i++; i <= size; i += i & -i) {
fenw[i] += v;
changes.push_back(i);
}
}
int prefix_sum(int r) {
int ans = 0;
for (; r > 0; r -= r & -r) {
ans += fenw[r];
}
return ans;
}
int suffix_sum(int l) {
return prefix_sum(size) - prefix_sum(l);
}
void clear() {
for (int i : changes) {
fenw[i] = 0;
}
changes.clear();
}
};
const int N = 120000;
vector<pair<int, int>> graph[N]; // (v, t)
vector<tuple<int, int, int, int>> Share[N]; // (a, b, t, id)
vector<tuple<int, int, int, int>> Query[N]; // (a, b, t, id)
vector<tuple<int, int, int>> Count[N]; // (u, t, id)
int sz[N], answer[2 * N], type[N], last[N];
bool used[N];
fenwick bit;
gp_hash_table<int, int, CustomHash> s, edge;
void sizes(int u, int p) {
sz[u] = 1;
for (auto [v, t] : graph[u]) {
if (v != p && !used[v]) {
sizes(v, u);
sz[u] += sz[v];
}
}
}
int centroid(int u, int p, int n) {
for (auto [v, t] : graph[u]) {
if (v != p && !used[v] && sz[v] > n / 2) {
return centroid(v, u, n);
}
}
return u;
}
void DFS(int u, int p, vector<int>& comp) {
comp.push_back(u);
for (auto [v, t] : graph[u]) {
if (v != p && !used[v]) {
DFS(v, u, comp);
}
}
}
void explore(int u, int p, int time) {
s.insert({u, u});
if (type[u] == 0 || type[u] == 1) {
bit.add(edge[u], 1);
}
for (auto [v, t] : graph[u]) {
if (v != p && !used[v] && t <= time) {
if (type[u] == 0) {
type[v] = (last[u] == -1 ? 0 : (last[u] < t ? 1 : 2));
} else if (type[u] == 1) {
type[v] = (last[u] < t ? 1 : 3);
} else if (type[u] == 2) {
type[v] = (last[u] > t ? 2 : 3);
} else {
type[v] = 3;
}
last[v] = t;
explore(v, u, time);
}
}
}
void find_centroids(int u, int p) {
gp_hash_table<int, int, CustomHash> first, to;
edge[u] = -1;
for (auto [v, t] : graph[u]) {
if (v != p && !used[v]) {
sizes(v, u);
to[v] = centroid(v, u, sz[v]);
}
}
for (auto [v, t] : graph[u]) {
if (v != p && !used[v]) {
vector<int> comp;
DFS(v, u, comp);
for (int x : comp) {
first[x] = v;
edge[x] = t;
}
}
}
for (auto &[k, v] : first) {
v = to[v];
}
first[u] = INT_MIN;
vector<int> D;
for (auto [a, b, t, id] : Share[u]) {
D.push_back(t);
}
for (auto [a, b, t, id] : Query[u]) {
D.push_back(t);
}
for (auto [a, t, id] : Count[u]) {
D.push_back(t);
}
sort(D.begin(), D.end());
D.resize(unique(D.begin(), D.end()) - D.begin());
int share_pos = 0, query_pos = 0, count_pos = 0;
s.insert({u, u});
type[u] = 0;
last[u] = -1;
for (int t : D) {
while (share_pos < (int)Share[u].size() && get<2>(Share[u][share_pos]) <= t) {
auto [a, b, _t, id] = Share[u][share_pos];
if (first[a] == first[b]) {
Share[first[a]].emplace_back(a, b, _t, id);
}
if (s.find(b) != s.end()) {
swap(a, b);
}
if (s.find(a) != s.end()) {
if (type[a] == 0) {
type[b] = (last[a] == -1 ? 0 : (last[a] < t ? 1 : 2));
} else if (type[a] == 1) {
type[b] = (last[a] < t ? 1 : 3);
} else if (type[a] == 2) {
type[b] = (last[a] > t ? 2 : 3);
} else {
type[b] = 3;
}
last[b] = t;
explore(b, a, t);
}
share_pos++;
}
while (query_pos < (int)Query[u].size() && get<2>(Query[u][query_pos]) <= t) {
auto [a, b, _t, id] = Query[u][query_pos];
if (a == b) {
answer[id] = INT_MAX;
} else if (first[a] == first[b]) {
Query[first[a]].emplace_back(a, b, _t, id);
} else {
bool good = true;
good &= s.find(a) != s.end() && s.find(b) != s.end();
good &= type[a] <= 1;
good &= type[b] == 0 || type[b] == 2;
good &= edge[a] == -1 || edge[b] == -1 || edge[a] > edge[b];
answer[id] = good ? INT_MAX : INT_MIN;
}
query_pos++;
}
while (count_pos < (int)Count[u].size() && get<1>(Count[u][count_pos]) <= t) {
auto [a, _t, id] = Count[u][count_pos];
if (a != u) {
Count[first[a]].emplace_back(a, _t, id);
}
if (s.find(a) != s.end()) {
if (type[a] == 0 || type[a] == 2) {
answer[id] += bit.suffix_sum(edge[a] + 1) + 1;
}
}
count_pos++;
}
}
s.clear();
bit.clear();
edge.clear();
used[u] = true;
for (auto [v, t] : graph[u]) {
if (v != p && !used[v]) {
sizes(v, u);
find_centroids(centroid(v, u, sz[v]), u);
}
}
}
void solve() {
memset(used, 0, sizeof used);
memset(answer, 0, sizeof answer);
int n, k;
cin >> n >> k;
bit = fenwick(n);
int t = 0;
vector<tuple<int, int, int, int>> share_queries, query_queries;
vector<tuple<int, int, int>> count_queries;
for (int i = 0; i < n + k - 1; i++) {
char type;
cin >> type;
if (type == 'S') {
int a, b;
cin >> a >> b;
a--, b--;
t++;
graph[a].emplace_back(b, t);
graph[b].emplace_back(a, t);
share_queries.emplace_back(a, b, t, i);
} else if (type == 'Q') {
int a, d;
cin >> a >> d;
a--, d--;
query_queries.emplace_back(a, d, t, i - t);
} else {
int d;
cin >> d;
d--;
count_queries.emplace_back(d, t, i - t);
}
}
sizes(0, -1);
int c = centroid(0, -1, n);
Share[c] = share_queries;
Query[c] = query_queries;
Count[c] = count_queries;
find_centroids(c, -1);
for (int i = 0; i < k; i++) {
if (answer[i] == INT_MIN) {
cout << "no\n";
} else if (answer[i] == INT_MAX) {
cout << "yes\n";
} else {
cout << answer[i] << "\n";
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}