This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//
// Created by 42kangaroo on 07/02/2024.
//
#include "bits/stdc++.h"
using namespace std;
template<typename T>
using g_t = vector<vector<T>>;
struct Que {
char c;
int f, s;
string an;
};
struct BinL {
bool asc, desc;
int p, upVal, downVal;
};
struct Ed {
int a, b, w;
};
array<int, 12005> logT;
g_t<BinL> binL;
g_t<Ed> g;
vector<int> de;
void dfs(int n, int p, int d, vector<pair<int, int>> &pa) {
pa[n].first = p;
de[n] = d;
for (auto &e: g[n]) {
if (e.b == p) {
pa[n].second = e.w;
continue;
}
dfs(e.b, n, d + 1, pa);
}
}
BinL combine(const BinL &l, const BinL &r) {
BinL res{};
res.p = r.p;
res.upVal = r.upVal;
res.downVal = l.downVal;
res.asc = l.asc && r.asc && l.upVal > r.downVal;
res.desc = l.desc && r.desc && l.upVal < r.downVal;
return res;
}
void binLPrep(vector<pair<int, int>> &p) {
binL = g_t<BinL>(logT[p.size()] + 1, vector<BinL>(p.size()));
for (int i = 0; i < p.size(); ++i) {
binL[0][i] = {true, true, p[i].first, p[i].second, p[i].second};
}
for (int i = 1; i < binL.size(); ++i) {
for (int j = 0; j < p.size(); ++j) {
binL[i][j] = combine(binL[i - 1][j], binL[i - 1][binL[i - 1][j].p]);
}
}
}
bool connected(int i, int st, int en) {
if (st == en) return true;
bool sw = false;
if (de[st] < de[en]) {
sw = true;
swap(st, en);
}
int k = de[st] - de[en];
BinL biSt{true, true, -1, -1, -1};
BinL biEn{true, true, -1, -1, -1};
for (int j = 0; k; k >>= 1, ++j) {
if (k & 1) {
if (biSt.p == -1) {
biSt = binL[j][st];
} else {
biSt = combine(biSt, binL[j][st]);
}
st = biSt.p;
}
}
if (st == en) {
if (sw) {
return biSt.asc && biSt.downVal <= i;
} else {
return biSt.desc && biSt.upVal <= i;
}
}
for (int j = binL.size() - 1; j >= 0; j--) {
if (binL[j][st].p != binL[j][en].p) {
if (biSt.p == -1) {
biSt = binL[j][st];
} else {
biSt = combine(biSt, binL[j][st]);
}
st = biSt.p;
if (biEn.p == -1) {
biEn = binL[j][en];
} else {
biEn = combine(biEn, binL[j][en]);
}
en = biEn.p;
}
}
if (biSt.p == -1) {
biSt = binL[0][st];
} else {
biSt = combine(biSt, binL[0][st]);
}
if (biEn.p == -1) {
biEn = binL[0][en];
} else {
biEn = combine(biEn, binL[0][en]);
}
if (sw) {
swap(biEn, biSt);
}
return biSt.desc && biEn.asc && biSt.upVal < biEn.upVal && biEn.downVal <= i;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
logT[1] = 0;
for (int i = 2; i < logT.size(); ++i) {
logT[i] = logT[i / 2] + 1;
}
g = g_t<Ed>(n);
vector<Que> que(k + n - 1);
for (int i = 0; i < k + n - 1; ++i) {
char c;
cin >> c;
if (c == 'S') {
int a, b;
cin >> a >> b;
--a;
--b;
g[a].push_back({a, b, i});
g[b].push_back({b, a, i});
que[i] = {c, a, b, ""};
}
if (c == 'Q') {
int a, b;
cin >> a >> b;
--a;
--b;
que[i] = {c, a, b, ""};
}
if (c == 'C') {
int a;
cin >> a;
--a;
que[i] = {c, a, -1, ""};
}
}
vector<pair<int, int>> p(n, {0, 0});
de = vector<int>(n);
dfs(0, 0, 0, p);
binLPrep(p);
for (int i = 0; i < que.size(); ++i) {
if (que[i].c == 'Q') {
que[i].an = (connected(i, que[i].s, que[i].f) ? "yes" : "no");
}
}
for (int i = 0; i < que.size(); ++i) {
if (que[i].an != "") cout << que[i].an << "\n";
}
}
Compilation message (stderr)
servers.cpp: In function 'void binLPrep(std::vector<std::pair<int, int> >&)':
servers.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0; i < p.size(); ++i) {
| ~~^~~~~~~~~~
servers.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<BinL, std::allocator<BinL> >, std::allocator<std::vector<BinL, std::allocator<BinL> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 1; i < binL.size(); ++i) {
| ~~^~~~~~~~~~~~~
servers.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int j = 0; j < p.size(); ++j) {
| ~~^~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:131:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 12005>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 2; i < logT.size(); ++i) {
| ~~^~~~~~~~~~~~~
servers.cpp:166:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for (int i = 0; i < que.size(); ++i) {
| ~~^~~~~~~~~~~~
servers.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for (int i = 0; i < que.size(); ++i) {
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |