oj.uz

Submission #1093610

# Submission time Handle Problem Language Result Execution time Memory
1093610 2024-09-27T06:44:54 Z CDuong Inside information (BOI21_servers) C++17
80 / 100
 268 ms 28288 KB 
/*
#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) {}
};

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 n, q;
    cin >> n >> q;

    graph<int> g(n);
    vector<int> tpq(n + q), res(n + q);
    vector<vector<Query>> queries(n);
    for (int i = 0; i < n - 1 + q; ++i) {
        char ch;
        cin >> ch;
        if (ch == 'S') {
            int u, v;
            cin >> u >> v;
            --u, --v;
            g.link(u, v, i);
            tpq[i] = 0;
        }
        else if (ch == 'Q') {
            int u, v;
            cin >> u >> v;
            --u, --v;
            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]));
    }

    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];
        }
    };

    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 {
                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 {
        vis_dfs[u] = pw;
        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();
            rst.pop_back();
            vis_dfs[u] = n + q;
            fenw.update(pw, -1);
        }
    };

    auto centroid = [&](auto self, int u) -> void {
        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();
                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 {
                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";
        }
    }

#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{
      |                  ^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4952 KB Output is correct
2 Correct 25 ms 6228 KB Output is correct
3 Correct 23 ms 5972 KB Output is correct
4 Correct 25 ms 6236 KB Output is correct
5 Correct 27 ms 6416 KB Output is correct
6 Correct 23 ms 6188 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4952 KB Output is correct
2 Correct 25 ms 6228 KB Output is correct
3 Correct 23 ms 5972 KB Output is correct
4 Correct 25 ms 6236 KB Output is correct
5 Correct 27 ms 6416 KB Output is correct
6 Correct 23 ms 6188 KB Output is correct
7 Correct 20 ms 4956 KB Output is correct
8 Incorrect 27 ms 5712 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 17 ms 5212 KB Output is correct
2 Correct 109 ms 22004 KB Output is correct
3 Correct 121 ms 22132 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5212 KB Output is correct
2 Correct 109 ms 22004 KB Output is correct
3 Correct 121 ms 22132 KB Output is correct
4 Correct 16 ms 5212 KB Output is correct
5 Correct 91 ms 22656 KB Output is correct
6 Correct 69 ms 21040 KB Output is correct
7 Correct 70 ms 21116 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5212 KB Output is correct
2 Correct 216 ms 27092 KB Output is correct
3 Correct 196 ms 27148 KB Output is correct
4 Correct 161 ms 28288 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5212 KB Output is correct
2 Correct 216 ms 27092 KB Output is correct
3 Correct 196 ms 27148 KB Output is correct
4 Correct 161 ms 28288 KB Output is correct
5 Correct 16 ms 5212 KB Output is correct
6 Correct 197 ms 26732 KB Output is correct
7 Correct 175 ms 27908 KB Output is correct
8 Correct 190 ms 26372 KB Output is correct
9 Correct 191 ms 26372 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5212 KB Output is correct
2 Correct 151 ms 21724 KB Output is correct
3 Correct 137 ms 20756 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5212 KB Output is correct
2 Correct 151 ms 21724 KB Output is correct
3 Correct 137 ms 20756 KB Output is correct
4 Correct 16 ms 5208 KB Output is correct
5 Correct 165 ms 21444 KB Output is correct
6 Correct 153 ms 20484 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5212 KB Output is correct
2 Correct 208 ms 26968 KB Output is correct
3 Correct 205 ms 27188 KB Output is correct
4 Correct 162 ms 28168 KB Output is correct
5 Correct 16 ms 5208 KB Output is correct
6 Correct 148 ms 21768 KB Output is correct
7 Correct 144 ms 20740 KB Output is correct
8 Correct 141 ms 21252 KB Output is correct
9 Correct 157 ms 21252 KB Output is correct
10 Correct 245 ms 24328 KB Output is correct
11 Correct 255 ms 24328 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5212 KB Output is correct
2 Correct 208 ms 26968 KB Output is correct
3 Correct 205 ms 27188 KB Output is correct
4 Correct 162 ms 28168 KB Output is correct
5 Correct 16 ms 5208 KB Output is correct
6 Correct 148 ms 21768 KB Output is correct
7 Correct 144 ms 20740 KB Output is correct
8 Correct 141 ms 21252 KB Output is correct
9 Correct 157 ms 21252 KB Output is correct
10 Correct 245 ms 24328 KB Output is correct
11 Correct 255 ms 24328 KB Output is correct
12 Correct 16 ms 5208 KB Output is correct
13 Correct 220 ms 26944 KB Output is correct
14 Correct 185 ms 28192 KB Output is correct
15 Correct 192 ms 26632 KB Output is correct
16 Correct 189 ms 26372 KB Output is correct
17 Correct 16 ms 5212 KB Output is correct
18 Correct 155 ms 21764 KB Output is correct
19 Correct 147 ms 20488 KB Output is correct
20 Correct 139 ms 21172 KB Output is correct
21 Correct 147 ms 21252 KB Output is correct
22 Correct 260 ms 23812 KB Output is correct
23 Correct 252 ms 24584 KB Output is correct
24 Correct 268 ms 24840 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5212 KB Output is correct
2 Correct 29 ms 6492 KB Output is correct
3 Correct 22 ms 5984 KB Output is correct
4 Correct 26 ms 6488 KB Output is correct
5 Correct 33 ms 6608 KB Output is correct
6 Correct 25 ms 6484 KB Output is correct
7 Correct 16 ms 5212 KB Output is correct
8 Correct 106 ms 22944 KB Output is correct
9 Correct 91 ms 22912 KB Output is correct
10 Correct 17 ms 5212 KB Output is correct
11 Correct 191 ms 27140 KB Output is correct
12 Correct 195 ms 27144 KB Output is correct
13 Correct 166 ms 28208 KB Output is correct
14 Correct 17 ms 5212 KB Output is correct
15 Correct 152 ms 21608 KB Output is correct
16 Correct 145 ms 20552 KB Output is correct
17 Correct 149 ms 21160 KB Output is correct
18 Correct 143 ms 21120 KB Output is correct
19 Correct 234 ms 24516 KB Output is correct
20 Correct 229 ms 24440 KB Output is correct
21 Correct 106 ms 23048 KB Output is correct
22 Correct 106 ms 22208 KB Output is correct
23 Correct 134 ms 21380 KB Output is correct
24 Correct 136 ms 21508 KB Output is correct
25 Correct 192 ms 25092 KB Output is correct
26 Correct 145 ms 20744 KB Output is correct
27 Correct 140 ms 20748 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5212 KB Output is correct
2 Correct 29 ms 6492 KB Output is correct
3 Correct 22 ms 5984 KB Output is correct
4 Correct 26 ms 6488 KB Output is correct
5 Correct 33 ms 6608 KB Output is correct
6 Correct 25 ms 6484 KB Output is correct
7 Correct 16 ms 5212 KB Output is correct
8 Correct 106 ms 22944 KB Output is correct
9 Correct 91 ms 22912 KB Output is correct
10 Correct 17 ms 5212 KB Output is correct
11 Correct 191 ms 27140 KB Output is correct
12 Correct 195 ms 27144 KB Output is correct
13 Correct 166 ms 28208 KB Output is correct
14 Correct 17 ms 5212 KB Output is correct
15 Correct 152 ms 21608 KB Output is correct
16 Correct 145 ms 20552 KB Output is correct
17 Correct 149 ms 21160 KB Output is correct
18 Correct 143 ms 21120 KB Output is correct
19 Correct 234 ms 24516 KB Output is correct
20 Correct 229 ms 24440 KB Output is correct
21 Correct 106 ms 23048 KB Output is correct
22 Correct 106 ms 22208 KB Output is correct
23 Correct 134 ms 21380 KB Output is correct
24 Correct 136 ms 21508 KB Output is correct
25 Correct 192 ms 25092 KB Output is correct
26 Correct 145 ms 20744 KB Output is correct
27 Correct 140 ms 20748 KB Output is correct
28 Correct 17 ms 5208 KB Output is correct
29 Incorrect 28 ms 5972 KB Extra information in the output file
30 Halted 0 ms 0 KB -