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>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
struct dsu{
vector<int> sz, m, p;
int n; bool t;
dsu(int ns, bool ts){
n = ns; t = ts;
p.resize(n + 1);
sz.resize(n + 1);
m.resize(n + 1);
for (int i = 1; i <= n; i++){
p[i] = m[i] = i;
sz[i] = 1;
}
}
int get(int v){
if (p[v] != v){
p[v] = get(p[v]);
}
return p[v];
}
int f(int x, int y){
if (t) return max(x, y);
return min(x, y);
}
int q(int v){
return m[get(v)];
}
void unite(int x, int y){
x = get(x); y = get(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
p[x] = y;
sz[y] += sz[x];
m[y] = f(m[y], m[x]);
}
};
struct NC{
vector<int> a;
void add(int x){
a.pb(x);
}
int get(int x){
int out = 1;
for (int i: a) out += (i > x);
return out;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
struct query{
char t;
int x, y;
};
int n, q; cin>>n>>q;
q += (n - 1);
vector<query> qs(q + 1);
vector<int> g[n + 1];
for (int i = 1; i <= q; i++){
cin>>qs[i].t>>qs[i].x;
if (qs[i].t != 'C') cin>>qs[i].y;
if (qs[i].t == 'S'){
g[qs[i].x].pb(qs[i].y);
g[qs[i].y].pb(qs[i].x);
}
}
vector<int> sz(n + 1), d(n + 1), h(n + 1), p(n + 1);
function<void(int, int)> dfs = [&](int v, int pr){
p[v] = pr;
sz[v] = 1;
for (int i: g[v]){
if (i == pr) continue;
d[i] = d[v] + 1;
dfs(i, v);
if (sz[i] > sz[h[v]]){
h[v] = i;
}
sz[v] += sz[i];
}
};
dfs(1, 0);
vector<int> head(n + 1), pos(n + 1);
int timer = 0;
function<void(int, int)> dfs_hld = [&](int v, int k){
head[v] = k;
pos[v] = ++timer;
if (!h[v]) return;
dfs_hld(h[v], k);
for (int i: g[v]){
if (pos[i]) continue;
dfs_hld(i, i);
}
};
dfs_hld(1, 1);
auto pr = [&](int a, int b){
return (d[a] > d[b]) ? a : b;
};
vector<int> f(n + 1);
dsu T1(n, 1), T2(n, 0);
auto lca = [&](int x, int y){
while (head[x] != head[y]){
if (d[head[x]] > d[head[y]]){
swap(x, y);
}
y = p[head[y]];
}
return ((d[x] > d[y]) ? y : x);
};
const arr3 zr = {0, 0, 0};
auto check = [&](int x, int y){
int a = lca(x, y), pre = 0, mini = q + 1, maxi = 0;
while (true){
// xl > ... > xr
if (d[head[x]] > d[a]){
int l = pos[head[x]], r = pos[x];
if (!f[r] || T2.q(r) > l || f[r] < pre) return zr;
x = p[head[x]];
mini = min(mini, f[r]);
maxi = max(maxi, f[l]);
pre = f[l];
}
else {
int l = pos[a] + 1, r = pos[x];
if (l <= r && (!f[r] || T2.q(r) > l || f[r] < pre)) return zr;
if (l <= r){
pre = f[l];
mini = min(mini, f[r]);
maxi = max(maxi, f[l]);
}
break;
}
}
vector<pii> all;
while (true){
// xl < ... < xr
if (d[head[y]] > d[a]){
int l = pos[head[y]], r = pos[y];
all.pb({l, r});
y = p[head[y]];
}
else {
int l = pos[a] + 1, r = pos[y];
if (l <= r) all.pb({l, r});
break;
}
}
reverse(all.begin(), all.end());
for (auto [l, r]: all){
if (!f[l] || T1.q(l) < r || f[l] < pre) return zr;
mini = min(mini, f[l]);
maxi = max(maxi, f[r]);
pre = f[r];
}
arr3 ret = {1, mini, maxi};
return ret;
};
// Arvid's Decomposition
vector<bool> used(n + 1);
function<void(int, int)> fill_sz = [&](int v, int pr){
sz[v] = 1;
for (int i: g[v]){
if (i == pr || used[i]) continue;
fill_sz(i, v);
sz[v] += sz[i];
}
};
function<int(int, int, int&)> find = [&](int v, int pr, int& S){
for (int i: g[v]){
if (i == pr || used[i]) continue;
if (2 * sz[i] >= S) return find(i, v, S);
}
return v;
};
vector<int> par(n + 1), dd(n + 1);
function<void(int, int, int)> arvid = [&](int v, int p, int s){
fill_sz(v, 0);
int k = find(v, 0, sz[v]);
par[k] = p;
dd[k] = s;
used[k] = 1;
for (int i: g[k]){
if (used[i]) continue;
arvid(i, k, s + 1);
}
};
arvid(1, 0, 0);
NC T[n + 1];
map<int, bool> mp[n + 1];
auto get = [&](int v){
int t = par[v], out = T[v].get(0);
while (t > 0){
arr3 d = check(v, t);
if (d[0]){
out += T[t].get(d[2]);
}
t = par[t];
}
return out;
};
auto add = [&](int x){
int t = par[x];
while (t > 0){
arr3 d = check(t, x);
if (mp[t].find(x) == mp[t].end() && d[0]){
mp[t][x] = 1;
T[t].add(d[1]);
}
t = par[t];
}
};
auto upd = [&](int a, int b, int i){
int v = pos[pr(a, b)];
f[v] = i;
if (f[v - 1] && f[v - 1] < f[v]) T1.unite(v, v - 1);
if (v != n && f[v] < f[v + 1]) T1.unite(v, v + 1);
if (f[v - 1] > f[v]) T2.unite(v, v - 1);
if (v != n && f[v + 1] && f[v] > f[v + 1]) T2.unite(v, v + 1);
add(a); add(b);
};
for (int i = 1; i <= q; i++){
if (qs[i].t == 'S'){
upd(qs[i].x, qs[i].y, i);
}
else if (qs[i].t == 'Q'){
int a = qs[i].x, b = qs[i].y;
cout<<(check(b, a)[0] ? "yes" : "no")<<"\n";
}
else {
cout<<get(qs[i].x)<<"\n";
}
}
}
# | 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... |