This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define MN 120071
#define MK 20
using namespace std;
int n, k;
vector<pair<int, int> > L0[MN];
vector<int> L[MN];
vector<tuple<int, int, int, int> > Queries;
namespace BASIC {
int Niv[MN], Val[MN], Par[MN], NiceUp[MN];
int Maxi[MK][MN], Nice[2][MK][MN], Stramos[MK][MN];
void init() {
///aleg rad arbitrar in 1
function<void(int, int, int, int)> dfs0 = [&](int u, int p, int niv, int val) {
Val[u] = val;
Niv[u] = niv;
Par[u] = p;
for(auto &[it, w] : L0[u]) if(it != p) {
dfs0(it, u, niv + 1, w);
}
if(Niv[u] > 1) NiceUp[u] = Val[u] < Val[p];
};
dfs0(1, 0, 0, 0);
for(int i = 1; i <= n; ++i) Stramos[0][i] = Par[i];
for(int k = 1; k < MK; ++k) {
for(int i = 1; i <= n; ++i)
Stramos[k][i] = Stramos[k-1][Stramos[k-1][i]];
}
for(int i = 1; i <= n; ++i)
Nice[0][0][i] = NiceUp[i] ^ 1, Nice[1][0][i] = NiceUp[i];
for(int d = 0; d < 2; ++d) {
for(int k = 1; k < MK; ++k) {
for(int i = 1; i <= n; ++i) {
Nice[d][k][i] = Nice[d][k-1][i] & Nice[d][k-1][Stramos[k-1][i]];
}
}
}
for(int i = 1; i <= n; ++i)
Maxi[0][i] = Val[i];
for(int k = 1; k < MK; ++k)
for(int i = 1; i <= n; ++i)
Maxi[k][i] = max(Maxi[k-1][i], Maxi[k-1][Stramos[k-1][i]]);
}
bool is_okay(int u, int v) { ///!!! ORDER IS VERY IMPORTANT U => V
bool rez = 1;
if(Niv[u] > Niv[v]) {
for(int k = MK - 1; k >= 0; --k) {
if((Niv[u] - Niv[v] - 1) & (1 << k)) {
rez &= Nice[1][k][u];
u = Stramos[k][u];
}
}
if(Par[u] != v) rez &= Nice[1][0][u];
u = Par[u];
} else if (Niv[u] < Niv[v]) {
for(int k = MK - 1; k >= 0; --k) {
if((Niv[v] - Niv[u] - 1) & (1 << k)) {
rez &= Nice[0][k][v];
// printf("debug %d %d %d -- ", k, v, rez);
//printf("debug %d %d %d\n", Nice[0][0][v], Nice[0][1][v], Stramos[1][v]);
v = Stramos[k][v];
}
}
if(Par[v] != u) rez &= Nice[0][0][v];
v = Par[v];
}
///acum sunt la acelasi nivel
assert(Niv[u] == Niv[v]);
if(v == u || !rez) return rez;
for(int k = MK - 1; k >= 0; --k) {
if(Stramos[k][u] != Stramos[k][v]) {
rez &= Nice[0][k][v];
rez &= Nice[1][k][u];
v = Stramos[k][v];
u = Stramos[k][u];
}
}
if(u != v) rez &= Val[u] < Val[v];
return rez;
}
int max_on_path(int u, int v) {
int rez = 0;
if(Niv[u] < Niv[v]) swap(u, v);
if(Niv[u] != Niv[v])
for(int k = MK - 1; k >= 0; --k)
if((Niv[u] - Niv[v] - 1) & (1 << k)) {
rez = max(rez, Maxi[k][u]);
u = Stramos[k][u];
}
if(Niv[u] != Niv[v]) {
rez = max(rez, Maxi[0][u]);
u = Par[u];
}
assert(Niv[u] == Niv[v]);
for(int k = MK - 1; k >= 0; --k)
if(Stramos[k][u] != Stramos[k][v]) {
rez = max(rez, Maxi[k][u]);
rez = max(rez, Maxi[k][v]);
u = Stramos[k][u];
v = Stramos[k][v];
}
if(u != v) rez = max({rez, Val[u], Val[v]});
return rez;
}
}
int main() {
//cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for(int i = 1, a, b; i <= n + k - 1; ++i) {
char tip;
cin >> tip;
if(tip == 'S') {
cin >> a >> b;
L0[a].push_back({b, i});
L0[b].push_back({a, i});
} else if(tip == 'Q') {
cin >> a >> b;
Queries.push_back({0, a, b, i});
} else {
cin >> a;
Queries.push_back({1, a, 0, i});
}
}
BASIC::init();
for(auto &[tip, a, b, id] : Queries) {
if(tip == 0) {
int ok = BASIC::is_okay(b, a);
ok &= BASIC::max_on_path(b, a) < id;
cout << (ok ? "yes\n" : "no\n");
}
}
return 0;
}
# | 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... |