| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 863534 | Cyber_Wolf | A Difficult(y) Choice (BOI21_books) | C++17 | 0 ms | 0 KiB |
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;
#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;
bool inc;
bool dec;
Node()
{
f = l = 0;
inc = dec = 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.inc = (a.inc && b.inc && a.l < b.f);
c.dec = (a.dec && b.dec && a.l > b.f);
return c;
}
void build(lg node, lg lr, lg hr)
{
if(lr == hr)
{
seg[node].inc = seg[node].dec = 1;
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;
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[b] > depth[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(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')
{
lg _lca = lca(a, b);
lg cur = 1;
while(head[b] != head[_lca] && cur)
{
cur &= get(1, 1, n, loc[head[b]], loc[b]).inc;
b = p[head[b]];
}
cur &= get(1, 1, n, loc[_lca], loc[b]).inc;
while(head[a] != head[_lca] && cur)
{
cur &= get(1, 1, n, loc[head[a]], loc[a]).dec;
a = p[head[a]];
}
cur &= get(1, 1, n, loc[_lca], loc[a]).dec;
cout << (cur ? "yes\n" : "no\n");
}
}
}