#include <bits/stdc++.h>
using namespace std;
#define lg long long
#define mid (lr+hr)/2
const lg N = 2e5+5;
vector<array<lg, 2>> adj[N];
lg head[N], in[N], out[N], tmp, sz[N], p[N], euler[N], co[N], loc[N], depth[N];
struct Node{
lg f;
lg l;
lg sz;
lg mnm;
bool inc;
bool dec;
Node()
{
sz = 1;
f = l = 0;
inc = dec = 0;
mnm = 0;
}
} seg[N << 2];
//cost, first, last, increase, decrease
Node fake()
{
Node e;
e.f = -1;
return e;
}
Node merge(Node a, Node b)
{
if(a.f == -1) return b;
if(b.f == -1) return a;
Node c;
c.f = a.f;
c.l = b.l;
c.sz = a.sz+b.sz;
c.inc = (a.inc && b.inc && (a.l < b.f || a.l == -2 || b.f == -2));
c.dec = (a.dec && b.dec && (a.l > b.f || a.l == -2 || b.f == -2));
c.mnm = min(a.mnm, b.mnm);
if(c.mnm == -2 && c.f != -2) c.inc = c.dec = 0;
if(b.f == -2) c.inc = c.dec = 0;
return c;
}
void build(lg node, lg lr, lg hr)
{
if(lr == hr)
{
seg[node].inc = seg[node].dec = 1;
seg[node].l = seg[node].f = -2;
seg[node].sz = 1;
seg[node].mnm = seg[node].l;
return;
}
build(node << 1, lr, mid);
build(node << 1 | 1, mid+1, hr);
seg[node] = merge(seg[node << 1], seg[node << 1 | 1]);
return;
}
void update(lg node, lg lr, lg hr, lg idx, lg val)
{
if(lr > idx || hr < idx) return ;
if(lr == hr)
{
seg[node].f = seg[node].l = val;
seg[node].mnm = seg[node].l;
return ;
}
update(node << 1, lr, mid, idx, val);
update(node << 1 | 1, mid+1, hr, idx, val);
seg[node] = merge(seg[node << 1], seg[node << 1 | 1]);
return;
}
Node get(lg node, lg lr, lg hr, lg lq, lg hq)
{
if(lq > hr || lr > hq) return fake();
if(lq <= lr && hr <= hq) return seg[node];
return merge(get(node << 1, lr, mid, lq, hq), get(node << 1 | 1, mid+1, hr, lq, hq));
}
void dfs(lg src, lg par = -1)
{
sz[src] = 1;
for(auto [it, c] : adj[src])
{
if(it == par) continue;
depth[it] = depth[src]+1;
p[it] = src;
co[it] = c;
dfs(it, src);
sz[src] += sz[it];
}
return ;
}
void dfs2(lg src, lg par = -1)
{
in[src] = ++tmp;
euler[tmp] = src;
loc[src] = tmp;
if(p[src] == adj[src][0][0]) reverse(adj[src].begin(), adj[src].end());
for(auto &it : adj[src])
{
if(it[0] == par)
{
continue;
}
if(sz[it[0]] > sz[adj[src][0][0]]) swap(adj[src][0], it);
}
for(auto [it, c] : adj[src])
{
if(it == par)
{
continue;
}
head[it] = (it == adj[src][0][0] ? head[src] : it);
dfs2(it, src);
}
out[src] = tmp;
}
lg lca(lg a, lg b)
{
while(head[a] != head[b])
{
if(depth[head[b]] > depth[head[a]]) swap(a, b);
a = p[head[a]];
}
if(depth[b] > depth[a]) swap(a, b);
return b;
}
int main()
{
#ifdef CYBER
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
lg n, k;
cin >> n >> k;
vector<array<lg, 3>> que;
lg id = 1;
k += n-1;
while(k--)
{
char c;
cin >> c;
if(c == 'S')
{
lg u, v;
cin >> u >> v;
que.push_back({c, u, v});
adj[u].push_back({v, id});
adj[v].push_back({u, id});
id++;
}
else if(c == 'Q')
{
lg u, v;
cin >> u >> v;
que.push_back({c, u, v});
}
else{
lg u;
cin >> u;
que.push_back({c, u, 0});
}
}
dfs(1);
head[1] = 1;
p[1] = 1;
dfs2(1);
// cout << "head in out sz p co depth loc\n";
// for(int i = 1; i <= n; i++)
// {
// cout << head[i] << ' ' << in[i] << ' ' << out[i] << ' ' << sz[i] << ' ' << p[i] << ' ' << co[i] << ' ' << depth[i] << ' ' << loc[i] << '\n';
// }
// for(int i = 1; i <= n; i++) cout << euler[i] << ' ';
// cout << '\n';
// for(int i = 1; i <= n; i++)
// {
// for(int j = 1; j <= n; j++)
// {
// cout << lca(i, j) << ' ';
// }
// cout << '\n';
// }
build(1, 1, n);
// for(int i = 1; i <= n; i++ ) cout << euler[i] << ' ';
// cout << '\n';
for(auto [c, a, b] : que)
{
// cout << c << ' ' << a << ' ' << b << '\n';
if(c == 'S')
{
if(p[a] == b) swap(a, b);
update(1, 1, n, loc[b], co[b]);
}
else if(c == 'Q')
{
swap(a, b);
lg _lca = lca(a, b);
lg cur = 1;
lg la = 1e18;
Node o;
while(head[b] != head[_lca] && cur)
{
o = get(1, 1, n, loc[head[b]], loc[b]);
// cout << b << ' ';
cur &= (o.l < la);
la = o.f;
cur &= o.inc;
cur &= (o.mnm > -2);
// cout << "MNM: " << o.mnm << '\n';
b = p[head[b]];
}
// cout << b << ' ' << _lca << '\n';
// cout << "DEC " << cur << ' ';
o = get(1, 1, n, loc[_lca], loc[b]);
cur &= o.inc;
// cout << "DEC " << cur << ' ';
if(_lca != b) cur &= (o.l < la);
// cout << "DEC " << cur << ' ';
la = -1e18;
while(head[a] != head[_lca] && cur)
{
o = get(1, 1, n, loc[head[a]], loc[a]);
// cout << a << ' ';
cur &= (o.l > la);
la = o.f;
cur &= o.dec;
cur &= (o.mnm > -2);
// cout << "MNM: " << o.mnm << '\n';
a = p[head[a]];
}
// cout << a << ' ' << _lca << '\n';
o = get(1, 1, n, loc[_lca], loc[a]);
// cout << "DEC " << cur << ' ';
cur &= o.dec;
// cout << "DEC " << cur << ' ';
if(_lca != a) cur &= (o.l > la);
// cout << "DEC " << cur << ' ';
cout << (cur ? "yes\n" : "no\n");
}
// for(int i = 1; i <= n; i++)
// {
// lg x = get(1, 1, n, i, i).f;
// if(x > 1e15) cout << "inf ";
// else cout << x << ' ';
// }
// cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
51644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
51644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
51644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
51644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
51644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
51644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
51700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
51700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
51696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
51696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
51644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
51644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
