/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;
template<bool ALLOW_NON_PREFIX_QUERY, class T, class F, class I>
struct fenwick_tree{
int n;
vector<T> data;
F TT;
T T_id;
I Tinv;
fenwick_tree(F TT, T T_id, I Tinv): TT(TT), T_id(T_id), Tinv(Tinv){ }
fenwick_tree &operator=(const fenwick_tree &fw){
n = fw.n;
data = fw.data;
}
// O(n)
void build(int n){
assert(n >= 0);
this->n = n;
data.assign(n, T_id);
}
// O(n)
void build(int n, T x){
assert(n >= 0);
this->n = n;
data.assign(n, x);
for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = TT(data[i + (i & -i) - 1], data[i - 1]);
}
// O(n)
template<class U>
void build(const vector<U> &a){
n = (int)a.size();
data.resize(n);
copy(a.begin(), a.end(), data.begin());
for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = TT(data[i + (i & -i) - 1], data[i - 1]);
}
// O(log(n))
void update(int p, T x){
assert(0 <= p && p < n);
for(++ p; p <= n; p += p & -p) data[p - 1] = TT(data[p - 1], x);
}
// O(log(n))
void set(int p, T x){
update(p, TT(x, Tinv(query(p))));
}
// O(log(n))
T prefix(int r) const{
assert(0 <= r && r <= n);
T s = T_id;
for(; r > 0; r -= r & -r) s = TT(s, data[r - 1]);
return s;
}
// O(log(n))
T query(int l, int r) const{
static_assert(ALLOW_NON_PREFIX_QUERY);
assert(0 <= l && l <= r && r <= n);
if(l == r) return T_id;
T sum_minus = T_id, sum_plus = T_id;
for(; l < r; r -= r & -r) sum_plus = TT(sum_plus, data[r - 1]);
for(; r < l; l -= l & -l) sum_minus = TT(sum_minus, data[l - 1]);
return TT(sum_plus, Tinv(sum_minus));
}
// O(log(n))
T query(int p) const{
static_assert(ALLOW_NON_PREFIX_QUERY);
return query(p, p + 1);
}
// O(log(n))
T query_all() const{
return prefix(n);
}
// pred(sum[0, r)) is T, T, ..., T, F, F, ..., F, returns max r with T
// O(log(n))
int max_pref(auto pred) const{
assert(pred(T_id));
int p = 0;
T sum = T_id;
for(auto i = __lg(n + 1); i >= 0; -- i) if(p + (1 << i) <= n && pred(TT(sum, data[p + (1 << i) - 1]))){
sum = TT(sum, data[p + (1 << i) - 1]);
p += 1 << i;
}
return p;
}
template<class output_stream>
friend output_stream &operator<<(output_stream &out, const fenwick_tree &fw){
out << "{";
for(auto i = 0; i < fw.n; ++ i){
out << fw.query(i);
if(i != fw.n - 1) out << ", ";
}
return out << '}';
}
};
template<class T, class F, class I>
auto make_fenwick_tree(F TT, T T_id, I Tinv){
return fenwick_tree<true, T, F, I>(TT, T_id, Tinv);
}
template<class T>
auto make_fenwick_tree_sum(){
return fenwick_tree<true, T, plus<>, negate<>>(plus<>(), T{0}, negate<>());
}
template<class T>
auto make_fenwick_tree_product(){
auto inverse = [](const T &x){ return 1 / x; };
return fenwick_tree<true, T, multiplies<>, decltype(inverse)>(multiplies<>(), T{1}, inverse);
}
template<class T>
auto make_fenwick_tree_min(){
auto TT = [&](const T &x, const T &y)->T{ return min(x, y); };
return fenwick_tree<false, T, decltype(TT), negate<>>(TT, numeric_limits<T>::max(), negate<>());
}
template<class T>
auto make_fenwick_tree_max(){
auto TT = [&](const T &x, const T &y)->T{ return max(x, y); };
return fenwick_tree<false, T, decltype(TT), negate<>>(TT, numeric_limits<T>::max(), negate<>());
}
template<class T>
struct graph{
using Weight_t = T;
struct Edge_t{
int from, to;
T cost;
};
int n;
vector<Edge_t> edge;
vector<vector<int>> adj;
function<bool(int)> ignore;
graph(int n = 1): n(n), adj(n){
assert(n >= 1);
}
graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
assert(n >= 1);
if(undirected){
for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
}
else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
}
graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
assert(n >= 1);
if(undirected){
for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
}
else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
}
graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
assert(n >= 1);
for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
}
graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
assert(n >= 1);
for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
}
int add_vertex(){
adj.emplace_back();
return n ++;
}
int operator()(int u, int id) const{
#ifdef LOCAL
assert(0 <= id && id < (int)edge.size());
assert(edge[id].from == u || edge[id].to == u);
#endif
return u ^ edge[id].from ^ edge[id].to;
}
int link(int u, int v, T w = {}){ // insert an undirected edge
int id = (int)edge.size();
adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
return id;
}
int orient(int u, int v, T w = {}){ // insert a directed edge
int id = (int)edge.size();
adj[u].push_back(id), edge.push_back({u, v, w});
return id;
}
vector<int> neighbor(int u, int exclude = -1) const{
vector<int> res;
for(auto id: adj[u]){
if(id == exclude || ignore && ignore(id)) continue;
res.push_back(operator()(u, id));
}
return res;
}
void clear(){
for(auto [u, v, w]: edge){
adj[u].clear();
adj[v].clear();
}
edge.clear();
ignore = {};
}
graph transpose() const{ // the transpose of the directed graph
graph res(n);
for(auto id = 0; id < (int)edge.size(); ++ id){
if(ignore && ignore(id)) continue;
res.orient(edge[id].to, edge[id].from, edge[id].cost);
}
return res;
}
int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
return (int)adj[u].size();
}
// The adjacency list is sorted for each vertex.
vector<vector<int>> get_adjacency_list() const{
vector<vector<int>> res(n);
for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
if(ignore && ignore(id)) continue;
res[(*this)(u, id)].push_back(u);
}
return res;
}
void set_ignoration_rule(const function<bool(int)> &f){
ignore = f;
}
void reset_ignoration_rule(){
ignore = nullptr;
}
friend ostream &operator<<(ostream &out, const graph &g){
for(auto id = 0; id < (int)g.edge.size(); ++ id){
if(g.ignore && g.ignore(id)) continue;
auto &e = g.edge[id];
out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
}
return out;
}
};
struct Query {
int v, val, qid;
Query(int v, int val, int qid) : v(v), val(val), qid(qid) {}
};
struct T1 {
int res;
int mn, mx;
};
void solve() {
int n, q;
cin >> n >> q;
graph<int> g(n);
vector<int> tpq(n + q), res(n + q);
vector<vector<Query>> queries(n);
int cq = 0;
for (int i = 0; i < n - 1 + q; ++i) {
char ch;
cin >> ch;
if (ch == 'S') {
int u, v;
cin >> u >> v;
--u, --v;
// cout << u << " " << v << " " << i << endl;
g.link(u, v, i);
tpq[i] = 0;
}
else if (ch == 'Q') {
int u, v;
cin >> u >> v;
--u, --v;
// if (++cq == 7704) {
// cout << i << " " << v << " " << u << endl;
// }
queries[v].emplace_back(u, i, i);
tpq[i] = 1;
}
else {
int u;
cin >> u;
--u;
queries[u].emplace_back(-1, i, i);
tpq[i] = 2;
}
}
for (int i = 0; i < n; ++i) {
reverse(all(g.adj[i]));
// for (int j = 1; j < isz(g.adj[i]); ++j) {
// assert(g.edge[g.adj[i][j]].cost < g.edge[g.adj[i][j - 1]].cost);
// }
}
int tot_sz = 0;
vector<bool> vis(n);
vector<int> sz(n);
auto get_sz = [&](auto self, int u, int _pid) -> void {
sz[u] = 1;
for (auto id : g.adj[u]) if (id != _pid and not vis[g(u, id)]) {
int v = g(u, id);
self(self, v, id);
sz[u] += sz[v];
}
};
// for (int i = 0; i < n; ++i) {
// for (auto [u, val, qid] : queries[i]) {
// cout << i << " " << u << " " << val << endl;
// }
// }
auto find_cen = [&](auto self, int u, int _pid) -> int {
for (auto id : g.adj[u]) if (id != _pid and not vis[g(u, id)]) {
int v = g(u, id);
if (sz[v] > (tot_sz >> 1)) {
return self(self, v, id);
}
}
return u;
};
auto get_cen = [&](int v) -> int {
get_sz(get_sz, v, -1);
tot_sz = sz[v];
return find_cen(find_cen, v, -1);
};
auto fenw = make_fenwick_tree_sum<int>();
fenw.build(n + q);
vector<int> vis_dfs(n, n + q);
vector<pair<int, int>> rst;
auto dfs1 = [&](auto self, int u, int _pid, int pw) -> void {
for (auto [v, val, qid] : queries[u]) {
if (v == -1) {
res[qid] += fenw.prefix(val);
}
else {
// if (qid == 7706) {
// cout << vis_dfs[v] << " " << val << endl;
// }
// cout << u << " -> " << v << " " << vis_dfs[v] << " " << val << endl;
res[qid] |= (vis_dfs[v] <= val);
}
}
for (auto id : g.adj[u]) if (id != _pid and not vis[g(u, id)] and g.edge[id].cost < pw) {
int v = g(u, id);
self(self, v, id, g.edge[id].cost);
}
};
auto add = [&](int u, int pw) -> void {
// cout << "add: " << u << " " << pw << endl;
vis_dfs[u] = pw;
// if (u == 19) {
// cout << u << " " << pw << endl;
// // return;
// }
fenw.update(pw, 1);
rst.emplace_back(u, pw);
};
auto dfs2 = [&](auto self, int u, int _pid, int pw) -> void {
add(u, pw);
for (auto id : g.adj[u]) if (id != _pid and not vis[g(u, id)] and g.edge[id].cost > pw) {
int v = g(u, id);
self(self, v, id, g.edge[id].cost);
}
};
auto reset = [&]() -> void {
while (not rst.empty()) {
auto [u, pw] = rst.back();
// cout << "del: " << u << " " << pw << endl;
rst.pop_back();
vis_dfs[u] = n + q;
fenw.update(pw, -1);
}
};
auto centroid = [&](auto self, int u) -> void {
// cout << "centroid: " << u << endl;
vis[u] = true;
for (auto id : g.adj[u]) if (not vis[g(u, id)]) {
int v = g(u, id);
add(u, g.edge[id].cost);
dfs1(dfs1, v, -1, g.edge[id].cost);
{
auto [u, pw] = rst.back();
// cout << "del: " << u << " " << pw << endl;
rst.pop_back();
vis_dfs[u] = n + q;
fenw.update(pw, -1);
}
dfs2(dfs2, v, -1, g.edge[id].cost);
}
add(u, 0);
for (auto [v, val, qid] : queries[u]) {
if (v == -1) {
res[qid] += fenw.prefix(val);
}
else {
// if (qid == 7706) {
// cout << vis_dfs[v] << " " << val << endl;
// }
// cout << u << " -> " << v << " " << vis_dfs[v] << " " << val << endl;
res[qid] |= (vis_dfs[v] <= val);
}
}
reset();
for (auto id : g.adj[u]) if (not vis[g(u, id)]) {
int v = g(u, id);
int nxt_cen = get_cen(v);
self(self, nxt_cen);
}
};
int cen = get_cen(0);
centroid(centroid, cen);
for (int i = 0; i < n + q - 1; ++i) {
if (tpq[i] == 1) {
cout << (res[i] ? "yes" : "no") << "\n";
}
else if (tpq[i] == 2) {
cout << res[i] << "\n";
}
}
cout << endl;
assert(res[7706]);
}
signed main() {
#ifndef CDuongg
if (fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
Compilation message
servers.cpp:84:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
84 | int max_pref(auto pred) const{
| ^~~~
servers.cpp: In function 'void solve()':
servers.cpp:255:9: warning: unused variable 'cq' [-Wunused-variable]
255 | int cq = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
5204 KB |
Output is correct |
| 2 |
Runtime error |
30 ms |
10904 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
5204 KB |
Output is correct |
| 2 |
Runtime error |
30 ms |
10904 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
9304 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
9304 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
9304 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
9304 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
9344 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
9344 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
9416 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
9416 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
5388 KB |
Output is correct |
| 2 |
Runtime error |
29 ms |
10836 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
5388 KB |
Output is correct |
| 2 |
Runtime error |
29 ms |
10836 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
