#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
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;
set<int> s;
map<int, int> 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);
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) {
map<int, int> 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);
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.count(b)) {
swap(a, b);
}
if (s.count(a)) {
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.count(a) && s.count(b);
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.count(a)) {
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();
}
Compilation message
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from servers.cpp:3:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
73 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
74 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
75 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
76 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
77 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
91 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
101 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
