#include <iostream>
#include <chrono>
#include <vector>
#define maxn 1000005
#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;
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")
using namespace std;
struct query
{
char type;
int u , v;
query(){};
query(char _type , int _u , int _v)
{
type = _type;
u = _u;
v = _v;
}
};
int n , q;
vector <int> v[maxn];
vector <query> queries;
void read()
{
cin >> n >> q;
char type;
int u , _v;
for(int i = 0; i < q; i++)
{
cin >> type;
if(type == 'S')
{
cin >> u >> _v;
v[u].pb(_v);
v[_v].pb(u);
queries.push_back({type , u , _v});
}
if(type == 'Q')
{
cin >> u >> _v;
queries.push_back({type , u , _v});
}
if(type == 'C')
queries.push_back({type , u , -1});
}
}
int bin_lift[maxlog][maxn];
int sz[maxn];
bool used[maxn];
int depth[maxn];
void dfs(int node , int parent)
{
///sz[node] = 1;
///used[node] = true;
for(int nb : v[node])
{
if(nb == parent)
continue;
/**if(used[nb] == true)
continue;*/
bin_lift[0][nb] = node;
depth[nb] = depth[node] + 1;
dfs(nb , node);
}
///return sz[node];
}
void calc_bin()
{
for(int power = 1; power < maxlog; power++)
for(int i = 1; i <= n; i++)
bin_lift[power][i] = bin_lift[power - 1][bin_lift[power - 1][i]];
}
int get_lca(int a , int b)
{
if(depth[a] < depth[b])
swap(a , b);
for(int power = maxlog - 1; power > -1; power--)
if((depth[a] - depth[b]) >= (1 << power))
a = bin_lift[power][a];
if(a == b)
return a;
for(int power = maxlog - 1; power > -1; power--)
if(bin_lift[power][a] != bin_lift[power][b])
{
a = bin_lift[power][a];
b = bin_lift[power][b];
}
return bin_lift[0][a];
}
int calc_sz(int node , int parent)
{
sz[node] = 1;
for(int nb : v[node])
{
if(nb == parent)
continue;
if(used[nb] == true)
continue;
sz[node] += calc_sz(nb , node);
}
return sz[node];
}
int get_centroid(int node , int parent , int cur_sz)
{
for(int nb : v[node])
{
if(nb == parent)
continue;
if(used[nb] == true)
continue;
if(sz[nb] > cur_sz / 2)
return get_centroid(nb , node , cur_sz);
}
return node;
}
int _prev[maxn];
int centroid_depth[maxn];
void centroid_decomposition(int node , int parent)
{
node = get_centroid(node, -1 , calc_sz(node , -1));
_prev[node] = parent;
centroid_depth[node] = parent == -1 ? 0 : centroid_depth[parent] + 1;
used[node] = true;
for(int nb : v[node])
{
if(used[nb] == true)
continue;
centroid_decomposition(nb , node);
}
used[node] = false;
}
int hld_sz[maxn] , heavy[maxn];
int leader[maxn];
int hld(int node , int parent)
{
hld_sz[node] = 1;
heavy[node] = -1;
leader[node] = node;
for(int nb : v[node])
{
if(nb == parent)
continue;
hld_sz[node] += hld(nb , node);
if(heavy[node] < 0 || hld_sz[nb] > hld_sz[heavy[node]])
heavy[node] = nb;
}
return hld_sz[node];
}
struct segment_tree
{
int _n;
vector <int> tree;
vector <int> pom;
segment_tree(){};
segment_tree(int __n)
{
_n = __n;
tree = vector <int> (4 * n , 0);
}
void update(int node , int l , int r , int qval , int qpos)
{
if(qpos > r || l > qpos)
return;
if(qpos <= l && r <= qpos)
{
tree[node] += qval;
return;
}
int mid = (l + r) / 2;
update(node * 2 , l , mid , qval , qpos);
update(node * 2 + 1 , mid + 1 , r , qval , qpos);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int qu(int node , int l , int r , int qpos)
{
if(qpos > r)
return 0;
if(qpos <= l)
return tree[node];
int mid = (l + r) / 2;
return qu(node * 2 , l , mid , qpos) + qu(node * 2 + 1 , mid + 1 , r , qpos);
}
void _update(int qpos)
{
update(1 , 0 , n - 1 , 1 , lower_bound(pom.begin() , pom.end() , qpos) - pom.begin());
}
int query(int qpos)
{
return qu(1 , 0 , n - 1 , lower_bound(pom.begin() , pom.end() , qpos) - pom.begin());
}
void initialise()
{
tree = vector <int> (4 * n , 0);
}
};
segment_tree _tree[maxn];
int up[maxn][2] , down[maxn];
int idx[maxn];
void initialisation()
{
centroid_decomposition(1 , -1);
for(int node = 1; node <= n; node++)
{
for(int nb : v[node])
if(centroid_depth[nb] > centroid_depth[node])
_tree[node]._n++;
_tree[node].initialise();
}
dfs(1 , -1);
calc_bin();
hld(1 , -1);
for(int node = 1; node <= n; node++)
if(bin_lift[0][node] == 0 || heavy[bin_lift[0][node]] != node)
for(int nb = node; nb != -1; nb = heavy[nb])
leader[nb] = node;
for(int i = 1; i <= n; i++)
{
up[i][0] = i;
up[i][1] = i;
idx[i] = i + 1;
down[i] = i;
}
}
int get_idx(int a , int b)
{
return a == b? 0 : idx[depth[a] < depth[b] ? a : b];
}
int get_last_from_path(int a , int b)
{
if(a == b)
return a;
int lca = get_lca(a , b);
if(lca != b)
return bin_lift[0][b];
int ans = a;
for(int power = maxlog - 1; power > -1; power--)
if(depth[ans] - depth[lca] - 1 >= (1 << power))
ans = bin_lift[power][ans];
return ans;
}
bool check_has(int a , int b)
{
if(a == b)
return true;
int lca = get_lca(a , b);
if(depth[up[a][0]] > depth[lca])
return false;
int pom_node = b;
int pom = -1;
while(leader[pom_node] != leader[lca])
{
pom = leader[pom_node];
pom_node = bin_lift[0][leader[pom_node]];
}
if(b != pom_node && depth[up[b][1]] < pom_node)
return false;
if(depth[down[lca]] > depth[pom_node])
return false;
if(pom_node != lca && pom == -1 && get_idx(pom , pom_node) > idx[pom_node])
return false;
if(a == lca)
return true;
if(b == lca)
return true;
int pom1 = get_last_from_path(a , lca);
int pom2 = get_last_from_path(b , lca);
if(idx[pom1] > idx[pom2])
return true;
}
void rec(int a , int b , int c , int val)
{
up[a][1] = val;
for(int nb : v[a])
{
if(nb == b)
continue;
if(get_idx(a , nb) >= c)
continue;
rec(nb , a , get_idx(a , nb) , val);
}
}
int moment = 0;
void answer()
{
initialisation();
for(int i = 0; i < queries.size(); i++)
{
if(queries[i].type == 'S')
{
moment++;
if(centroid_depth[queries[i].u] > centroid_depth[queries[i].v])
swap(queries[i].u , queries[i].v);
if(depth[queries[i].u] > depth[queries[i].v])
swap(queries[i].u , queries[i].v);
idx[queries[i].v] = moment;
up[queries[i].v][0] = up[queries[i].u][0];
if(heavy[queries[i].u] != queries[i].v)
rec(queries[i].v , queries[i].u , moment , queries[i].u);
else
down[queries[i].u] = down[queries[i].v];
if(centroid_depth[queries[i].u] > centroid_depth[queries[i].v])
swap(queries[i].u , queries[i].v);
_tree[queries[i].u].pom.pb(moment);
int pom_node = queries[i].u;
while(pom_node > 0)
{
if(check_has(queries[i].u , pom_node))
{
int first_node = get_last_from_path(queries[i].u , pom_node);
if(first_node == pom_node)
first_node = queries[i].v;
int pom = get_idx(pom_node , first_node);
_tree[pom_node]._update(pom);
}
pom_node = _prev[pom_node];
}
}
if(queries[i].type == 'Q')
if(check_has(queries[i].u , queries[i].v) == true)
cout << "yes" << endl;
else
cout << "no" << endl;
if(queries[i].type == 'C')
{
int pom_node = queries[i].u;
int ans = 0;
while(pom_node > 0)
{
if(check_has(pom_node , queries[i].u) == true)
{
int _last = get_last_from_path(queries[i].u , pom_node);
int pom = get_idx(_last , pom_node);
pom++;
ans += _tree[pom_node].query(pom) + 1;
}
pom_node = _prev[pom_node];
}
cout << ans << endl;
}
}
}
int main()
{
/**#ifdef ONLINE_JUDGE
freopen("taxi.in", "r", stdin);
freopen("taxi.out", "w", stdout);
#endif*/
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
read();
answer();
return 0;
}
Compilation message
servers.cpp: In function 'void answer()':
servers.cpp:418:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
418 | for(int i = 0; i < queries.size(); i++)
| ~~^~~~~~~~~~~~~~~~
servers.cpp:468:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
468 | if(queries[i].type == 'Q')
| ^
servers.cpp: In function 'bool check_has(int, int)':
servers.cpp:392:1: warning: control reaches end of non-void function [-Wreturn-type]
392 | }
| ^
servers.cpp:328:35: warning: array subscript -1 is below array bounds of 'int [1000005]' [-Warray-bounds]
328 | return a == b? 0 : idx[depth[a] < depth[b] ? a : b];
| ~~~~~~~^
servers.cpp:73:5: note: while referencing 'depth'
73 | int depth[maxn];
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
139240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
139240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
139124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
139124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
139200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
139200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
139040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
139040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
139064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
139064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
139160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
139160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
