//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) {
stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) {
string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
bool fst = 1; string res = "{";
for (const auto& x: v) {
if (!fst) res += ", ";
fst = 0; res += to_string(x);
}
res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 120010;
struct Fenwick {
int fen[MAXN * 2];
vector<int> his;
inline void add (int ind) {
for (ind += 2; ind; ind -= ind & -ind) {
his.push_back(ind);
fen[ind]++;
}
}
inline int get (int ind) {
int ret = 0;
for (ind += 2; ind < 2 * MAXN; ind += ind & -ind) {
ret += fen[ind];
}
return ret;
}
inline void clear () {
for (int i : his) {
fen[i] = 0;
}
his.clear();
}
} fen;
struct Par {
int v, lst, first;
bool inc, dec;
};
struct Query {
bool x;
int v, u, t;
bool ans0 = 0;
int ans1 = 0;
};
struct Event {
bool x;
int l, r, ind;
inline bool operator < (const Event& he) {
return r < he.r;
}
};
int n, q, sz[MAXN], out[MAXN];
vector<Par> par[MAXN];
vector<Query> query;
vector<Event> event[MAXN];
vector<pair<int, int>> adj[MAXN], query_add[MAXN];
bitset<MAXN> hide;
void dfs_size (int v, int p) {
sz[v] = 1;
for (auto [i, t] : adj[v]) {
if (!hide[i] && i != p) {
dfs_size(i, v);
sz[v] += sz[i];
}
}
}
int centroid (int v, int p, int curn) {
for (auto [i, t] : adj[v]) {
if (i != p && !hide[i] && sz[i] * 2 > curn) {
return centroid(i, v, curn);
}
}
return v;
}
void dfs_build (int v, int p, int cent, int lst, int first, bool inc, bool dec) {
par[v].push_back({cent, lst, first, inc, dec});
if (inc && first != -1) {
event[cent].push_back({0, first, lst});
}
for (auto [i, t] : adj[v]) {
if (i == p || hide[i]) {
continue;
}
bool tdec = dec && (lst == -1 || lst > t);
bool tinc = inc && (lst == -1 || lst < t);
dfs_build(i, v, cent, t, first == 0 ? t : first, tinc, tdec);
}
}
void decompose (int v) {
dfs_size(v, -1);
v = centroid(v, -1, sz[v]);
hide[v] = 1;
dfs_build(v, -1, v, -1, 0, 1, 1);
for (auto [i, t] : adj[v]) {
if (!hide[i]) {
decompose(i);
}
}
}
inline bool get0 (int v, int u, int t) {
vector<int> tmp;
for (auto& i : par[u]) {
tmp.push_back(i.v);
}
int lca;
sort(all(tmp));
for (auto& i : par[v]) {
if (binary_search(all(tmp), i.v)) {
lca = i.v;
break;
}
}
wis(u, v, lca);
bool ret = 1;
Par U, V;
for (auto& i : par[u]) {
if (i.v == lca) {
U = i;
ret &= i.dec;
}
}
for (auto& i : par[v]) {
if (i.v == lca) {
V = i;
ret &= i.inc;
ret &= i.lst < t;
}
}
ret &= U.first == 0 || V.first == 0 || U.first <= V.first;
wis(U.first, V.first);
return ret;
}
inline void get1 (int v, int t, int ind) {
for (auto& i : par[v]) {
if (i.dec && i.first < t) {
event[i.v].push_back({1, i.first, t, ind});
}
}
}
inline void finish (int v) {
sort(all(event[v]));
for (auto& i : event[v]) {
if (i.x == 0) {
fen.add(i.l);
}
else {
query[i.ind].ans1 += fen.get(i.l) + 1;
}
}
fen.clear();
}
int main() {
ios::sync_with_stdio(0);
#ifndef LOCAL
cin.tie(0);
#endif
cin >> n >> q;
query.reserve(q);
for (int i = 1; i < n + q; i++) {
char c;
cin >> c;
if (c == 'S') {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
else if (c == 'Q') {
int v, d;
cin >> v >> d;
v--, d--;
query.push_back({0, v, d, i});
}
else {
int d;
cin >> d;
d--;
query.push_back({1, d, -1, i});
}
}
decompose(0);
for (int i = 0; i < n; i++) {
reverse(all(par[i]));
}
for (int i = 0; i < q; i++) {
if (query[i].x == 0) {
query[i].ans0 = get0(query[i].v, query[i].u, query[i].t);
}
else {
get1(query[i].v, query[i].t, i);
}
}
for (int i = 0; i < n; i++) {
finish(i);
}
for (int i = 0; i < q; i++) {
if (query[i].x == 0) {
cout << (query[i].ans0 ? "yes" : "no") << '\n';
}
else {
cout << query[i].ans1 << '\n';
assert(false);
}
}
}
Compilation message
servers.cpp: In function 'bool get0(int, int, int)':
servers.cpp:34:18: warning: statement has no effect [-Wunused-value]
34 | #define wis(...) 0
| ^
servers.cpp:149:5: note: in expansion of macro 'wis'
149 | wis(u, v, lca);
| ^~~
servers.cpp:34:18: warning: statement has no effect [-Wunused-value]
34 | #define wis(...) 0
| ^
servers.cpp:166:5: note: in expansion of macro 'wis'
166 | wis(U.first, V.first);
| ^~~
servers.cpp:165:25: warning: 'V.Par::first' may be used uninitialized in this function [-Wmaybe-uninitialized]
165 | ret &= U.first == 0 || V.first == 0 || U.first <= V.first;
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~
servers.cpp:165:41: warning: 'U.Par::first' may be used uninitialized in this function [-Wmaybe-uninitialized]
165 | ret &= U.first == 0 || V.first == 0 || U.first <= V.first;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:159:9: warning: 'lca' may be used uninitialized in this function [-Wmaybe-uninitialized]
159 | if (i.v == lca) {
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
15304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
15304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
15324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
15324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
15344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
15344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
15380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
15380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
15328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
15328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
15352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
15352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
