Submission #1093604

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1093604	2024-09-27T06:35:10 Z	CDuong	Inside information (BOI21_servers)	C++17	80 / 100	291 ms	28756 KB

servers

/*
#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;
}

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;
      |         ^~

Subtask #1

2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	4444 KB	Output is correct
2	Correct	24 ms	4956 KB	Output is correct
3	Correct	22 ms	6224 KB	Output is correct
4	Correct	24 ms	6476 KB	Output is correct
5	Correct	26 ms	6572 KB	Output is correct
6	Correct	24 ms	6516 KB	Output is correct

Subtask #2

0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	4444 KB	Output is correct
2	Correct	24 ms	4956 KB	Output is correct
3	Correct	22 ms	6224 KB	Output is correct
4	Correct	24 ms	6476 KB	Output is correct
5	Correct	26 ms	6572 KB	Output is correct
6	Correct	24 ms	6516 KB	Output is correct
7	Correct	17 ms	5212 KB	Output is correct
8	Incorrect	28 ms	6148 KB	Extra information in the output file
9	Halted	0 ms	0 KB	-

Subtask #3

2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	4440 KB	Output is correct
2	Correct	107 ms	23168 KB	Output is correct
3	Correct	101 ms	23168 KB	Output is correct

Subtask #4

2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	4440 KB	Output is correct
2	Correct	107 ms	23168 KB	Output is correct
3	Correct	101 ms	23168 KB	Output is correct
4	Correct	16 ms	5212 KB	Output is correct
5	Correct	98 ms	22968 KB	Output is correct
6	Correct	65 ms	21036 KB	Output is correct
7	Correct	69 ms	21376 KB	Output is correct

Subtask #5

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	5208 KB	Output is correct
2	Correct	201 ms	27536 KB	Output is correct
3	Correct	204 ms	27492 KB	Output is correct
4	Correct	166 ms	28676 KB	Output is correct

Subtask #6

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	5208 KB	Output is correct
2	Correct	201 ms	27536 KB	Output is correct
3	Correct	204 ms	27492 KB	Output is correct
4	Correct	166 ms	28676 KB	Output is correct
5	Correct	16 ms	5208 KB	Output is correct
6	Correct	216 ms	27200 KB	Output is correct
7	Correct	174 ms	28428 KB	Output is correct
8	Correct	209 ms	26888 KB	Output is correct
9	Correct	196 ms	26884 KB	Output is correct

Subtask #7

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	5208 KB	Output is correct
2	Correct	158 ms	22276 KB	Output is correct
3	Correct	147 ms	21256 KB	Output is correct

Subtask #8

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	5208 KB	Output is correct
2	Correct	158 ms	22276 KB	Output is correct
3	Correct	147 ms	21256 KB	Output is correct
4	Correct	17 ms	5212 KB	Output is correct
5	Correct	161 ms	21860 KB	Output is correct
6	Correct	152 ms	20744 KB	Output is correct

Subtask #9

12.5 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	5200 KB	Output is correct
2	Correct	198 ms	27656 KB	Output is correct
3	Correct	209 ms	27672 KB	Output is correct
4	Correct	163 ms	28720 KB	Output is correct
5	Correct	17 ms	5212 KB	Output is correct
6	Correct	150 ms	22276 KB	Output is correct
7	Correct	147 ms	21252 KB	Output is correct
8	Correct	144 ms	21768 KB	Output is correct
9	Correct	144 ms	21764 KB	Output is correct
10	Correct	249 ms	24960 KB	Output is correct
11	Correct	249 ms	24780 KB	Output is correct

Subtask #10

12.5 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	5200 KB	Output is correct
2	Correct	198 ms	27656 KB	Output is correct
3	Correct	209 ms	27672 KB	Output is correct
4	Correct	163 ms	28720 KB	Output is correct
5	Correct	17 ms	5212 KB	Output is correct
6	Correct	150 ms	22276 KB	Output is correct
7	Correct	147 ms	21252 KB	Output is correct
8	Correct	144 ms	21768 KB	Output is correct
9	Correct	144 ms	21764 KB	Output is correct
10	Correct	249 ms	24960 KB	Output is correct
11	Correct	249 ms	24780 KB	Output is correct
12	Correct	22 ms	5208 KB	Output is correct
13	Correct	209 ms	27268 KB	Output is correct
14	Correct	177 ms	28424 KB	Output is correct
15	Correct	200 ms	26884 KB	Output is correct
16	Correct	222 ms	26884 KB	Output is correct
17	Correct	17 ms	5200 KB	Output is correct
18	Correct	157 ms	22024 KB	Output is correct
19	Correct	161 ms	20816 KB	Output is correct
20	Correct	151 ms	21412 KB	Output is correct
21	Correct	149 ms	21344 KB	Output is correct
22	Correct	287 ms	24072 KB	Output is correct
23	Correct	260 ms	24880 KB	Output is correct
24	Correct	291 ms	25348 KB	Output is correct

Subtask #11

17.5 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	5432 KB	Output is correct
2	Correct	26 ms	6492 KB	Output is correct
3	Correct	23 ms	6224 KB	Output is correct
4	Correct	26 ms	6480 KB	Output is correct
5	Correct	26 ms	6736 KB	Output is correct
6	Correct	29 ms	6564 KB	Output is correct
7	Correct	15 ms	5468 KB	Output is correct
8	Correct	111 ms	23272 KB	Output is correct
9	Correct	88 ms	23164 KB	Output is correct
10	Correct	16 ms	5212 KB	Output is correct
11	Correct	198 ms	27656 KB	Output is correct
12	Correct	208 ms	27524 KB	Output is correct
13	Correct	179 ms	28756 KB	Output is correct
14	Correct	17 ms	5212 KB	Output is correct
15	Correct	154 ms	22528 KB	Output is correct
16	Correct	152 ms	21256 KB	Output is correct
17	Correct	143 ms	21764 KB	Output is correct
18	Correct	149 ms	21748 KB	Output is correct
19	Correct	230 ms	24836 KB	Output is correct
20	Correct	238 ms	24836 KB	Output is correct
21	Correct	114 ms	23560 KB	Output is correct
22	Correct	107 ms	22788 KB	Output is correct
23	Correct	130 ms	21764 KB	Output is correct
24	Correct	142 ms	22024 KB	Output is correct
25	Correct	194 ms	25536 KB	Output is correct
26	Correct	149 ms	21256 KB	Output is correct
27	Correct	156 ms	21256 KB	Output is correct

Subtask #12

0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	5432 KB	Output is correct
2	Correct	26 ms	6492 KB	Output is correct
3	Correct	23 ms	6224 KB	Output is correct
4	Correct	26 ms	6480 KB	Output is correct
5	Correct	26 ms	6736 KB	Output is correct
6	Correct	29 ms	6564 KB	Output is correct
7	Correct	15 ms	5468 KB	Output is correct
8	Correct	111 ms	23272 KB	Output is correct
9	Correct	88 ms	23164 KB	Output is correct
10	Correct	16 ms	5212 KB	Output is correct
11	Correct	198 ms	27656 KB	Output is correct
12	Correct	208 ms	27524 KB	Output is correct
13	Correct	179 ms	28756 KB	Output is correct
14	Correct	17 ms	5212 KB	Output is correct
15	Correct	154 ms	22528 KB	Output is correct
16	Correct	152 ms	21256 KB	Output is correct
17	Correct	143 ms	21764 KB	Output is correct
18	Correct	149 ms	21748 KB	Output is correct
19	Correct	230 ms	24836 KB	Output is correct
20	Correct	238 ms	24836 KB	Output is correct
21	Correct	114 ms	23560 KB	Output is correct
22	Correct	107 ms	22788 KB	Output is correct
23	Correct	130 ms	21764 KB	Output is correct
24	Correct	142 ms	22024 KB	Output is correct
25	Correct	194 ms	25536 KB	Output is correct
26	Correct	149 ms	21256 KB	Output is correct
27	Correct	156 ms	21256 KB	Output is correct
28	Correct	17 ms	5208 KB	Output is correct
29	Incorrect	27 ms	6148 KB	Extra information in the output file
30	Halted	0 ms	0 KB	-