#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 = bl[i][v].merge_data(res);
}
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][lca[i-1][j]].merge_data(bl[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);
}else if (curlca == e){
ll diff = d[s]-d[curlca];
res = bl_lift(s,diff);
swap(res.isup, res.isdown);
}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(eres.isdown,eres.isup);
res = sres.merge_data(eres);
}
//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{
if (i.x == i.y){
cout << "yes\n";
}else{
cout << ((bl.qry(i.x,i.y,ctr) ? "yes" : "no")) << "\n";
}
}
}
}
};
int main(){
Solver mySolver;
mySolver.solve();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
81 ms |
3624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
81 ms |
3624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
66 ms |
3548 KB |
Output is correct |
| 2 |
Correct |
274 ms |
104544 KB |
Output is correct |
| 3 |
Correct |
351 ms |
104628 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
66 ms |
3548 KB |
Output is correct |
| 2 |
Correct |
274 ms |
104544 KB |
Output is correct |
| 3 |
Correct |
351 ms |
104628 KB |
Output is correct |
| 4 |
Incorrect |
67 ms |
4376 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
68 ms |
3620 KB |
Output is correct |
| 2 |
Correct |
283 ms |
105780 KB |
Output is correct |
| 3 |
Correct |
266 ms |
105976 KB |
Output is correct |
| 4 |
Correct |
356 ms |
105128 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
68 ms |
3620 KB |
Output is correct |
| 2 |
Correct |
283 ms |
105780 KB |
Output is correct |
| 3 |
Correct |
266 ms |
105976 KB |
Output is correct |
| 4 |
Correct |
356 ms |
105128 KB |
Output is correct |
| 5 |
Incorrect |
65 ms |
3632 KB |
Extra information in the output file |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
65 ms |
3660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
65 ms |
3660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
66 ms |
3636 KB |
Output is correct |
| 2 |
Correct |
310 ms |
105824 KB |
Output is correct |
| 3 |
Correct |
260 ms |
105892 KB |
Output is correct |
| 4 |
Correct |
390 ms |
105180 KB |
Output is correct |
| 5 |
Incorrect |
69 ms |
3544 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
66 ms |
3636 KB |
Output is correct |
| 2 |
Correct |
310 ms |
105824 KB |
Output is correct |
| 3 |
Correct |
260 ms |
105892 KB |
Output is correct |
| 4 |
Correct |
390 ms |
105180 KB |
Output is correct |
| 5 |
Incorrect |
69 ms |
3544 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
76 ms |
3556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
76 ms |
3556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
