#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define F first
#define S second
struct qry{
char type;
ll x,y;
qry(){}
};
struct data{
ll mn, mx;
bool isup, isdown;
// isup is increasing, isdown is decreasing
data(){
mn = -1; mx = -1; isup = isdown = false;
}
data(ll x){
mn = mx = x;
isup = isdown = true;
}
data merge_data (const data& rhs){
data res;
res.mn = min(mn,rhs.mn);
res.mx = max(mx,rhs.mx);
res.isup == isup && rhs.isup && (mx < rhs.mn);
res.isdown = isdown && rhs.isdown && (mn > rhs.mx);
return res;
}
void print(){
cout << "mn: " << mn << " mx: " << mx << " isup: " << isup << " isdown: " << isdown << "\n";
}
};
class BinLift {
private:
vector<vector<data> > bl;
vvi lca;
vi p,w,d;
ll lift (ll v, ll x){
for (ll i = 0; 20 > i; i++){
ll bm = 1; bm <<= i;
if (x & bm) v = lca[i][v];
}
return v;
}
data bl_lift (ll v, ll x){
data res;
for (ll i = 0; 20 > i; i++){
ll bm = 1; bm <<= i;
if (x & bm){
if (res.mn == -1){
res = bl[i][v];
}else{
res = res.merge_data(bl[i][v]);
}
v = lca[i][v];
}
}
return res;
}
ll lca_qry (ll u, ll v){
if (d[u] > d[v]) swap(u,v);
// d[u] <= d[v]
// lift v
v = lift(v,d[v]-d[u]);
if (v == u) return v;
for (ll i = 19; i >= 0; i--){
if (lca[i][v] != lca[i][u]){
v = lca[i][v];
u = lca[i][u];
}
}
return p[v];
}
public:
BinLift(vi p,vi w,vi d): p(p), w(w), d(d){
ll n = p.size();
lca.assign(20,vi(n,-1));
lca[0] = p;
bl.assign(20, vector<data>(n));
for (ll i = 0; n > i; i++){
bl[0][i] = data(w[i]);
}
for (ll i = 1; 20 > i; i++){
for (ll j = 0; n > j; j++){
lca[i][j] = lca[i-1][j];
if (lca[i-1][j] != -1)
lca[i][j] = lca[i-1][lca[i-1][j]];
}
}
for (ll i = 1; 20 > i; i++){
for (ll j = 0; n > j; j++){
if (lca[i][j] == -1) continue;
bl[i][j] = bl[i-1][j].merge_data(bl[i-1][lca[i-1][j]]);
}
}
}
BinLift(){}
bool qry(ll s, ll e, ll t){
ll curlca = lca_qry(s,e);
data res;
if (curlca == s){
ll diff = d[e]-d[curlca];
res = bl_lift(e,diff);
swap(res.isup,res.isdown);
}else if (curlca == e){
ll diff = d[s]-d[curlca];
res = bl_lift(s,diff);
}else{
ll sd = d[s]-d[curlca];
ll ed = d[e]-d[curlca];
data sres = bl_lift(s,sd);
data eres = bl_lift(e,ed);
swap(sres.isdown,sres.isup);
res = eres.merge_data(sres);
}
//res.print();
return (res.isdown && res.mx <= t);
}
};
class Solver{
private:
ll n,k;
vector<qry> q;
vvii adjList;
vi p,w,d;
BinLift bl;
void dfs (ll v){
for (auto e: adjList[v]){
if (e.F != p[v]){
p[e.F] = v; w[e.F] = e.S; d[e.F] = d[v]+1; dfs(e.F);
}
}
}
public:
Solver(){
cin >> n >> k;
adjList.resize(n);
q.resize(n+k-1);
ll ctr = 0;
for (auto &i: q){
cin >> i.type;
if (i.type == 'C') cin >> i.x;
else{
cin >> i.x >> i.y;
i.x--; i.y--;
if (i.type == 'S'){
adjList[i.x].emplace_back(i.y,ctr);
adjList[i.y].emplace_back(i.x,ctr);
ctr++;
}
}
}
p.assign(n,-1);
w.assign(n,-1);
d.assign(n,0);
dfs(0);
bl = BinLift(p,w,d);
}
void solve(){
ll ctr = -1;
for (auto &i: q){
if (i.type == 'C') cout << "1\n";
else if (i.type == 'S') ctr++;
else{
cout << ((bl.qry(i.x,i.y,ctr) ? "yes" : "no")) << "\n";
}
}
}
};
int main(){
Solver mySolver;
mySolver.solve();
}
Compilation message
servers.cpp: In member function 'data data::merge_data(const data&)':
servers.cpp:34:38: warning: statement has no effect [-Wunused-value]
34 | res.isup == isup && rhs.isup && (mx < rhs.mn);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
4284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
4284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
4428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
4428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
4316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
4316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
4344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
4344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
4384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
4384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
4412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
4412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
