bool home = 1;
#include <bits/stdc++.h>
using namespace std;
const int N = 240000 + 7;
const int K = 20;
int n;
int k;
vector<pair<int, int>> gg[N];
vector<pair<int, int>> q2[N];
int q1[N];
int p[N];
int pskip[K][N];
int dep[N];
int euler_tour[2 * N];
int tour_sz;
int first_time_on_tour[N];
int last_time_on_tour[N];
int lg2[2 * N];
int idup[N];
//vector<int> g[N];
pair<int, int> tab_lca[2 * N][K];
vector<int> who_have_id[N];
int who_has_id[N];
void dfs_lca(int a, int par = 0)
{
p[a] = par;
euler_tour[++tour_sz] = a;
first_time_on_tour[a] = last_time_on_tour[a] = tour_sz;
vector<pair<int, int>> ngg;
for (auto& it : gg[a])
{
int b = it.first;
int i = it.second;
if (b == par) {
continue;
}
ngg.push_back(it);
who_has_id[i] = b;
idup[b] = i;
dep[b] = 1 + dep[a];
dfs_lca(b, a);
euler_tour[++tour_sz] = a;
last_time_on_tour[a] = tour_sz;
}
gg[a] = ngg;
}
void lcaTM()
{
dfs_lca(1);
for (int i = 2; i <= tour_sz; i++)
{
lg2[i] = 1 + lg2[i / 2];
}
for (int i = 1; i <= tour_sz; i++)
{
tab_lca[i][0] = { dep[euler_tour[i]], euler_tour[i] };
}
for (int k = 1; (1 << k) <= tour_sz; k++)
{
for (int i = 1; i + (1 << k) - 1 <= tour_sz; i++)
{
tab_lca[i][k] = min(tab_lca[i][k - 1], tab_lca[i + (1 << (k - 1))][k - 1]);
}
}
}
int lca(int a, int b)
{
if (first_time_on_tour[a] > last_time_on_tour[b])
{
swap(a, b);
}
a = first_time_on_tour[a];
b = last_time_on_tour[b];
int k = lg2[b - a + 1];
return min(tab_lca[a][k], tab_lca[b - (1 << k) + 1][k]).second;
}
int goup(int a, int cnt) {
assert(cnt >= 0);
for (int i = 0; i < K; i++) {
if (cnt & (1 << i)) {
a = pskip[i][a];
}
}
return a;
}
int sol[N];
int tp[N];
int inc[N];
int dcr[N];
int cnt[N];
void dfs2(int a) {
inc[a] = max(inc[a], 1);
dcr[a] = max(dcr[a], 1);
for (auto& it : gg[a]) {
int b = it.first;
if (b == p[a]) {
continue;
}
if (idup[a] < idup[b]) {
inc[b] = 1 + inc[a];
}
else {
dcr[b] = 1 + dcr[a];
}
dfs2(b);
} ///cout<<"vis "<<a<<" : "<<inc[a]<<" vs "<<dcr[a]<<"\n";
}
bool blocked[N];
int print[N];
vector<int> cq[N];
vector<pair<int, int>> realg[N];
int score[N];
int total_score;
int curpar[N];
int when[N];
int goval[N];
void compute_score(int a, int p = -1) {
score[a] = 1 + (int) cq[a].size();
for (auto &it : realg[a]) {
int b = it.first, i = it.second;
if (blocked[b] || b == p) {
continue;
}
compute_score(b, a);
score[a] += score[b];
}
}
int fndcen(int a, int p = -1) {
int mx = total_score - score[a];
for (auto &it : realg[a]) {
int b = it.first, i = it.second;
if (blocked[b] || b == p) {
continue;
}
mx = max(mx, score[b]);
}
if (mx <= total_score / 2) {
return a;
}
for (auto &it : realg[a]) {
int b = it.first, i = it.second;
if (blocked[b] || b == p) {
continue;
}
if (mx == score[b]) {
return fndcen(b, a);
}
}
assert(0);
}
void dfsfromcen(int a, int p, int group) {
curpar[a] = p;
for (auto &it : realg[a]) {
int b = it.first, i = it.second;
if (blocked[b] || b == p) {
continue;
}
when[b] = i;
dfsfromcen(b, a, group);
}
}
int kekdfs(int a, int p, int last, int t) {
int sol = 0;
for (auto &it : realg[a]) {
int b = it.first, i = it.second;
if (blocked[b] || b == p) {
continue;
}
if (last < i) {
if (i < t) {
sol++;
}
sol += kekdfs(b, a, i, t);
}
}
return sol;
}
vector<int> guys;
void dfsexplore(int a, int p, int group) {
for (auto &it : realg[a]) {
int b = it.first, i = it.second;
if (blocked[b] || b == p) {
continue;
}
dfsexplore(b, a, group);
}
if (p) {
///cout << a << " : " << p << "\n";
assert(curpar[a] == p);
for (auto &T : cq[a]) {
vector<int> vals;
int cur = a;
int guy = -1;
while (curpar[cur]) {
vals.push_back(when[cur]);
guy = cur;
cur = curpar[cur];
}
/// vals should be increasing
bool is_inc = 1;
for (int it = 1; it < (int) vals.size(); it++) {
is_inc &= (vals[it - 1] < vals[it]);
}
if (!is_inc) {
continue;
}
assert(!vals.empty());
assert(guy != -1);
int last_value = vals.back();
assert(last_value == goval[guy]);
if (last_value < T) {
print[T]++;
for (auto &oth_guy : guys) {
if (oth_guy != guy && goval[guy] < goval[oth_guy]) {
if (goval[oth_guy] < T) {
print[T]++;
}
assert(curpar[guy] == curpar[oth_guy]);
assert(curpar[curpar[guy]] == 0);
print[T] += kekdfs(oth_guy, curpar[guy], goval[oth_guy], T);
}
}
}
}
}
}
void cdecomp(int a) {
compute_score(a);
total_score = score[a];
a = fndcen(a);
guys.clear();
int group = 0;
int cnt_guys = 0;
for (auto &it : realg[a]) {
int b = it.first, i = it.second;
if (blocked[b]) {
continue;
}
cnt_guys++;
when[b] = i;
goval[b] = i;
guys.push_back(b);
dfsfromcen(b, a, i);
}
assert((int) guys.size() == cnt_guys);
curpar[a] = 0;
if (home) {
///cout << "centroid = " << a << "\n";
}
{
/// the case for a
for (auto &T : cq[a]) {
print[T] += kekdfs(a, 0, -1, T);
}
}
if (home) {
///cout << "done\n";
}
{
/// the case for the others and it also going through a
/// it stops at a
group = 0;
for (auto &it : realg[a]) {
int b = it.first, i = it.second;
if (blocked[b]) {
continue;
}
dfsexplore(b, a, i);
}
}
if (home) {
///cout << "really done\n";
}
blocked[a] = 1;
for (auto &it : realg[a]) {
int b = it.first, i = it.second;
if (blocked[b]) {
continue;
}
cdecomp(b);
}
}
int main() {
if (!home) {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
} else {
freopen("___input___.txt", "r", stdin);
}
cin >> n >> k;
int cnt3 = 0;
for (int i = 1; i <= n + k - 1; i++) {
string s;
cin >> s;
assert(s == "S" || s == "Q" || s == "C");
if (s == "S") {
tp[i] = 2;
int a, b;
cin >> a >> b;
///g[a].push_back(b);
///g[b].push_back(a);
gg[a].push_back({ b, i });
gg[b].push_back({ a, i });
sol[i] = -1;
}
if (s == "Q") {
int a, b;
cin >> a >> b;
if (a == b) {
tp[i] = 1;
sol[i] = 1;
}
else {
q2[a].push_back({ b, i });
tp[i] = 1;
sol[i] = -2;
}
}
if (s == "C") {
cnt3++;
int a;
cin >> a;
cq[a].push_back(i);
/// cout<<i<<" = "<<a<<"\n";
q1[i] = a;
sol[i] = -3;
tp[i] = 3;
}
}
for (int i = 1; i <= n; i++) {
realg[i] = gg[i];
}
lcaTM();
dfs2(1);
cdecomp(1);
/// solve q1 for the general case
for (int i = 1; i <= n; i++) {
pskip[0][i] = p[i];
}
for (int k = 1; k < K; k++) {
for (int i = 1; i <= n; i++) {
pskip[k][i] = pskip[k - 1][pskip[k - 1][i]];
}
}
for (int a = 1; a <= n; a++) {
for (auto& it : q2[a]) {
int b = it.first, i = it.second;
/**
**/
/// drumul de la b la a e crescator?
vector<int> guys_x, guys_y;
int x = a, y = b, z;
swap(x, y);
z = lca(x, y);
int last = -1;
if (y != z) {
last = idup[y];
}
else {
last = idup[goup(x, dep[x] - dep[z] - 1)];
}
bool ok = 1;
ok &= (inc[y] >= dep[y] - dep[z]);
ok &= (dcr[x] >= dep[x] - dep[z]);
if (x != z && y != z) {
ok &= (idup[goup(x, dep[x] - dep[z] - 1)] <= idup[goup(y, dep[y] - dep[z] - 1)]);
}
ok &= (last < i);
sol[i] = ok;
}
}
const int INF = (int)1e9 + 7;
int cnt_2 = 0;
int ciq = 0;
for (int i = 1; i <= n + k - 1 && cnt3 != 0; i++) {
if (tp[i] == 2) {
cnt_2++;
int cnt_down = max(1, inc[who_has_id[i]] - 1);
int vertex = who_has_id[i];
for (int j = 1; j <= cnt_down; j++) {
cnt[vertex]++;
vertex = p[vertex];
}
}
if (q1[i]) {
ciq++;
assert(tp[i] == 3);
int vertex = q1[i];
int ret = 1;
for (auto& it : gg[vertex]) {
int v2 = it.first;
ret += cnt[v2];
}
int cnt_down = min(dcr[q1[i]], dep[q1[i]]);
int down = 0;
for (int j = 1; j <= cnt_down; j++) {
ret += (idup[vertex] < i);
for (auto& it : gg[p[vertex]]) {
int v2 = it.first;
if (idup[vertex] < idup[v2]) {
ret += cnt[v2];
}
}
vertex = p[vertex];
}
sol[i] = ret;
}
}
if (cnt3) {
assert(cnt_2 == n - 1);
}
/**unsigned long long h = 0;
for (int i = 1; i <= n + k - 1; i++) h = 7777 * h + sol[i];
if (home) {
assert(h == 8758581888253777949);
cout << "good\n";
exit(0);
}**/
for (int i = 1; i <= n + k - 1; i++) {
if (tp[i] == 1) {
assert(sol[i] == 0 || sol[i] == 1);
if (sol[i] == 1) {
cout << "yes\n";
}
else {
cout << "no\n";
}
}
if (tp[i] == 3) {
cout << print[i] + 1 << "\n";
}
}
return 0;
}
Compilation message
servers.cpp: In function 'void compute_score(int, int)':
servers.cpp:131:23: warning: unused variable 'i' [-Wunused-variable]
131 | int b = it.first, i = it.second;
| ^
servers.cpp: In function 'int fndcen(int, int)':
servers.cpp:143:23: warning: unused variable 'i' [-Wunused-variable]
143 | int b = it.first, i = it.second;
| ^
servers.cpp:153:23: warning: unused variable 'i' [-Wunused-variable]
153 | int b = it.first, i = it.second;
| ^
servers.cpp: In function 'void dfsexplore(int, int, int)':
servers.cpp:197:23: warning: unused variable 'i' [-Wunused-variable]
197 | int b = it.first, i = it.second;
| ^
servers.cpp: In function 'void cdecomp(int)':
servers.cpp:297:23: warning: unused variable 'i' [-Wunused-variable]
297 | int b = it.first, i = it.second;
| ^
servers.cpp:250:7: warning: variable 'group' set but not used [-Wunused-but-set-variable]
250 | int group = 0;
| ^~~~~
servers.cpp: In function 'int main()':
servers.cpp:427:11: warning: unused variable 'down' [-Wunused-variable]
427 | int down = 0;
| ^~~~
servers.cpp:400:13: warning: unused variable 'INF' [-Wunused-variable]
400 | const int INF = (int)1e9 + 7;
| ^~~
servers.cpp:309:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
309 | freopen("___input___.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
28464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
28464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
28456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
28456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
