/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <chrono>
#include <set>
#include <vector>
#include <algorithm>
#define maxn 200005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;
using namespace std;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double pd;
struct edge
{
int to, x;
edge() {};
edge(int _to, int _x)
{
to = _to;
x = _x;
}
};
vector <edge> v[maxn];
bool cmp(edge e1, edge e2)
{
return e2.x < e1.x;
}
struct query
{
char type;
int x, y;
query() {};
query(char _type, int _x, int _y)
{
type = _type;
x = _x;
y = _y;
}
};
vector <query> queries;
int bin_lift[maxn][maxlog];
int depth[maxn];
void dfs_bin(int node, int par)
{
//sz[node] = 1;
for(edge nb : v[node])
{
if(nb.to == par)
continue;
depth[nb.to] = depth[node] + 1;
bin_lift[nb.to][0] = node;
dfs_bin(nb.to, node);
//sz[node] += sz[nb.to];
}
}
int n , q;
void calc()
{
for(int power = 1; power < maxlog; power++)
for(int i = 1; i <= n; i++)
bin_lift[i][power] = bin_lift[bin_lift[i][power - 1]][power - 1];
}
int get_lca(int a, int b)
{
if(depth[b] > depth[a])
swap(a, b);
for(int power = maxlog - 1; power > -1; power--)
if(depth[a] - depth[b] >= (1 << power))
a = bin_lift[a][power];
if(a == b)
return a;
for(int power = maxlog - 1; power > -1; power--)
if(bin_lift[a][power] != bin_lift[b][power])
{
a = bin_lift[a][power];
b = bin_lift[b][power];
}
return bin_lift[a][0];
}
int weight[maxn];
int up[maxn], down[maxn];
int timer , in[maxn] , out[maxn];
void dfs_sort(int node, int par)
{
timer++;
in[node] = timer;
sort(v[node].begin() , v[node].end() , cmp);
if(par == 1)
{
up[node] = par;
down[node] = par;
}
else
if(weight[node] > weight[par])
{
down[node] = down[par];
up[node] = par;
}
else
{
up[node] = up[par];
down[node] = par;
}
for(edge nb : v[node])
{
if(nb.to == par)
continue;
weight[nb.to] = nb.x;
dfs_sort(nb.to , node);
}
out[node] = timer;
}
int tree[maxn * 4];
int query(int node , int l , int r , int ql , int qr)
{
if(l > qr || r < ql)
return 0;
if(l >= ql && r <= qr)
return tree[node];
int mid = (l + r) / 2;
return query(node * 2 , l , mid , ql , qr) +
query(node * 2 + 1 , mid + 1 , r , ql , qr);
}
void update(int node , int l , int r , int qpos , int qval)
{
if(l == r)
{
tree[node] += qval;
return;
}
int mid = (l + r) / 2;
if(qpos <= mid)
update(node * 2 , l , mid , qpos , qval);
else
update(node * 2 + 1 , mid + 1 , r , qpos , qval);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int used[maxn];
int sz[maxn] , br;
vector <int> qu[maxn];
int find_centroid(int node , int par)
{
for(edge nb : v[node])
{
if(used[nb.to] == true)
continue;
if(nb.to == par)
continue;
if(sz[nb.to] > br / 2)
return find_centroid(nb.to , node);
}
return node;
}
vector <int> done;
void push_updates(int node , int par , int prev)
{
update(1 , 1 , maxn * 4 - 1 , prev , 1);
done.pb(prev);
for(edge nb : v[node])
{
if(nb.to == par)
continue;
if(used[nb.to] == true)
continue;
if(nb.x < prev)
continue;
push_updates(nb.to , node , nb.x);
}
}
int ans[maxn];
void dfs_update(int node , int par , int fix , int prev)
{
//cout << "innn" << endl;
for(int i : qu[node])
{
ans[i] += query(1 , 1 , maxn * 4 - 1 , 1 , i);
if(i > fix)
ans[i]++;
}
for(edge nb : v[node])
{
if(used[node] == true)
continue;
if(nb.x > prev)
continue;
if(nb.to == par)
continue;
dfs_update(nb.to , node , fix , nb.x);
}
}
void calc_sz(int node , int par)
{
sz[node] = 1;
for(edge nb : v[node])
{
if(used[nb.to] == true)
continue;
if(nb.to == par)
continue;
calc_sz(nb.to , node);
sz[node] += sz[nb.to];
}
}
void decompose(int node , int par)
{
//cout << "in" << endl;
for(int e : done)
update(1 , 1 ,maxn * 4 - 1 , e , -1);
done.clear();
calc_sz(node , -1);
br = sz[node];
int centroid = find_centroid(node , -1);
used[centroid] = true;
//cout << "here" << endl;
for(edge nb : v[centroid])
{
if(used[nb.to] == true)
continue;
//cout << "0" << endl;
dfs_update(nb.to , centroid , nb.x , nb.x);
//cout << "1" << endl;
push_updates(nb.to , centroid , nb.x);
//cout << "2" << endl;
}
//cout << "here" << endl;
for(int i : qu[centroid])
ans[i] += query(1 , 1 , maxn * 4 - 1 , 1 , i);
for(edge nb : v[centroid])
{
if(used[nb.to] == true)
continue;
decompose(nb.to , node);
}
}
int jump(int node , int steps)
{
for(int power = maxlog - 1; power > -1; power--)
if(steps >= (1 << power))
{
node = bin_lift[node][power];
steps -= (1 << power);
}
return node;
}
bool answer(int x , int y , int time)
{
if(x == y)
return true;
int lca = get_lca(x , y);
int cx = x , cy = y;
if(depth[cx] == depth[lca])
{
cy = jump(y , depth[cy] - depth[cx] - 1);
if(weight[cy] > time)
return false;
}
else
if(weight[cx] > time)
return false;
//cout << "kys" << endl;
if(depth[down[x]] <= depth[lca] && depth[up[y]] <= depth[lca])
{
if(depth[x] == depth[lca])
return true;
if(depth[y] == depth[lca])
return true;
x = jump(x , depth[x] - depth[lca] - 1);
y = jump(y , depth[y] - depth[lca] - 1);
if(weight[x] > weight[y])
return true;
}
return false;
}
void read_solve()
{
cin >> n >> q;
char type;
int x , y;
for(int i = 1; i <= n + q - 1; i++)
{
cin >> type;
if(type == 'S')
{
cin >> x >> y;
queries.push_back({type , x , y});
v[x].push_back({y , i});
v[y].push_back({x , i});
continue;
}
if(type == 'C')
{
cin >> x;
queries.push_back({type , x , -1});
qu[x].pb(i);
continue;
}
cin >> x >> y;
queries.push_back({type , x , y});
}
dfs_sort(1 , 1);
dfs_bin(1 , -1);
calc();
control
decompose(1 , -1);
control
for(int i = 1; i <= n + q - 1; i++)
ans[i]++;
for(int i = 1; i <= n + q - 1; i++)
if(queries[i].type == 'C')
cout << ans[i] << endl;
else
if(queries[i].type == 'Q')
cout << (answer(queries[i].x , queries[i].y , i)? "yes" : "no") << endl;
}
int main()
{
/**#ifdef ONLINE_JUDGE /// promeni
freopen("taxi.in", "r", stdin);
freopen("taxi.out", "w", stdout);
#endif*/
//ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
///startT = std::chrono::high_resolution_clock::now();
read_solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
15304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
15304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
15304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
15304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
15300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
15300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
15296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
15296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
15308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
15308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
15304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
15304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
