#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;
std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}
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 < n + q - 1; 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')
{
cin >> u;
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 > 0 ? centroid_depth[parent] + 1 : 0;
used[node] = true;
for(int nb : v[node])
{
if(used[nb] == true)
continue;
centroid_decomposition(nb , node);
}
used[node] = false;
}
int /**sz[maxn] , */heavy[maxn];
int leader[maxn];
int hld(int node , int parent)
{
sz[node] = 1;
heavy[node] = -1;
leader[node] = node;
for(int nb : v[node])
{
if(nb == parent)
continue;
sz[node] += hld(nb , node);
if(heavy[node] < 0 || sz[nb] > sz[heavy[node]])
heavy[node] = nb;
}
return 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(r < qpos || qpos < l)
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(r < qpos)
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)
{
cout << (lower_bound(pom.begin() , pom.end() , qpos) - pom.begin()) << endl;
return qu(1 , 0 , n - 1 , (lower_bound(pom.begin() , pom.end() , qpos) - pom.begin()));
}
void initialise()
{
///cout << _n << endl;
tree.resize(4 * (_n + 20));
fill(tree.begin() , tree.end() , 0);
}
};
segment_tree _tree[maxn];
int up[maxn][2] , down[maxn];
int idx[maxn];
void initialisation()
{
for(int i = 0; i < queries.size(); i++)
{
if(queries[i].type != 'S')
continue;
v[queries[i].u].pb(queries[i].v);
v[queries[i].v].pb(queries[i].u);
}
/**for(int i = 1; i <= n; i++)
{
cout << i << ": ";
for(int nb : v[i])
cout << nb << " ";
cout << endl;
}*/
centroid_decomposition(1 , -1);
/**for(int i = 1; i <= n; i++)
cout << _prev[i] << " ";
cout << endl;
for(int i = 1; i <= n; i++)
cout << centroid_depth[i] << " ";
cout << endl;*/
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();
/**for(int i = 1; i <= n; i++)
{
cout << i << ": ";
for(int j = 0; j <= 4; j++)
cout << bin_lift[j][i] << " ";
cout << endl;
}*/
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++)
cout << leader[i] << " ";
cout << endl;*/
/**for(int i = 1; i <= n; i++)
cout << heavy[i] << " ";
cout << endl;*/
/**cout << endl;
for(int i = 1; i <= n; i++)
cout << _prev[i] << " ";
cout << endl << endl;*/
for(int i = 1; i <= n; i++)
{
up[i][0] = i;
up[i][1] = i;
idx[i] = (maxn + 1);
down[i] = i;
}
}
int higher(int a , int b)
{
return depth[a] < depth[b]? b : a;
}
int lower(int a , int b)
{
return depth[a] > depth[b]? b : a;
}
int get_idx(int a , int b)
{
return a == b? 0 : idx[higher(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;
int dist = depth[a] - depth[lca] - 1;
for(int power = maxlog - 1; power > -1; power--)
if(dist >= (1 << power))
{
a = bin_lift[power][a];
dist -= (1 << power);
}
return a;
}
bool check_has(int a , int b)
{
if(a == b)
return true;
int lca = get_lca(a , b);
///cout << ":: " << lca << endl;
if(lower(up[a][0] , lca) != up[a][0])
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 && lower(up[b][1] , pom_node) != up[b][1])
return false;
/**if(a == 4 && b == 1)
cout << "|-> " << pom_node << " " << pom << endl;*/
if(higher(down[lca] , pom_node) != down[lca] || (pom_node != lca && pom != -1 && get_idx(pom , pom_node) > idx[pom_node]))
return false;
/**if(a == 4 && b == 1)
cout << "asdjas" << endl;*/
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;
return false;
}
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);
///cout << "-> " << queries[i].v << endl;
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];
/**cout << "----------" << endl;
for(int i = 1; i <= n; i++)
cout << idx[i] << " ";
cout << endl;
for(int i = 1; i <= n; i++)
cout << up[i][0] << " ";
cout << endl;
for(int i = 1; i <= n; i++)
cout << up[i][1] << " ";
cout << endl;
for(int i = 1; i <= n; i++)
cout << down[i] << " ";
cout << endl << "-----------" << endl;*/
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)
{
///cout << "__ " << queries[i].u << " " << pom_node << " " << check_has(queries[i].u , pom_node) << endl;
if(check_has(queries[i].u , pom_node) == true)
{
int first_node = get_last_from_path(queries[i].u , pom_node);
if(first_node == pom_node)
first_node = queries[i].v;
///cout << "* " << pom_node << " " << first_node << endl;
int pom = get_idx(pom_node , first_node);
///cout << pom << endl;
_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 << 1 / 0 << endl;
cout << "no" << endl;
}
}
if(queries[i].type == 'C')
{
///control
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) + 1;
cout << "--< " << pom_node << " " << pom << " " << _tree[pom_node]._n << " ";
ans += _tree[pom_node].query(pom) + 1;
}
pom_node = _prev[pom_node];
}
cout << ans << endl;
}
}
}
int main()
{
/**#ifdef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif*/
//ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
startT = std::chrono::high_resolution_clock::now();
read();
answer();
return 0;
}
Compilation message
servers.cpp: In function 'void initialisation()':
servers.cpp:310:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
310 | for(int i = 0; i < queries.size(); i++)
| ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'int get_last_from_path(int, int)':
servers.cpp:417:9: warning: unused variable 'ans' [-Wunused-variable]
417 | int ans = a;
| ^~~
servers.cpp: In function 'void answer()':
servers.cpp:507:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
507 | for(int i = 0; i < queries.size(); i++)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
137152 KB |
Output is correct |
| 2 |
Runtime error |
245 ms |
284840 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
137152 KB |
Output is correct |
| 2 |
Runtime error |
245 ms |
284840 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
137232 KB |
Output is correct |
| 2 |
Correct |
359 ms |
208140 KB |
Output is correct |
| 3 |
Correct |
313 ms |
208256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
137232 KB |
Output is correct |
| 2 |
Correct |
359 ms |
208140 KB |
Output is correct |
| 3 |
Correct |
313 ms |
208256 KB |
Output is correct |
| 4 |
Incorrect |
99 ms |
137360 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
137316 KB |
Output is correct |
| 2 |
Runtime error |
500 ms |
440976 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
137316 KB |
Output is correct |
| 2 |
Runtime error |
500 ms |
440976 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
137272 KB |
Output is correct |
| 2 |
Correct |
465 ms |
208792 KB |
Output is correct |
| 3 |
Correct |
558 ms |
208576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
137272 KB |
Output is correct |
| 2 |
Correct |
465 ms |
208792 KB |
Output is correct |
| 3 |
Correct |
558 ms |
208576 KB |
Output is correct |
| 4 |
Incorrect |
111 ms |
137576 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
137156 KB |
Output is correct |
| 2 |
Runtime error |
485 ms |
441020 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
137156 KB |
Output is correct |
| 2 |
Runtime error |
485 ms |
441020 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
137200 KB |
Output is correct |
| 2 |
Runtime error |
243 ms |
284932 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
137200 KB |
Output is correct |
| 2 |
Runtime error |
243 ms |
284932 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
