oj.uz

Submission #750538

# Submission time Handle Problem Language Result Execution time Memory
750538 2023-05-29T16:38:11 Z GrindMachine Inside information (BOI21_servers) C++17
100 / 100
 3017 ms 157044 KB 
// Om Namah Shivaya
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "yes" << endl
#define no cout << "no" << endl
 
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)
 
template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}
 
template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
 
/*

refs:
edi
some codes

type Q queries:

if val v is contained in node u, then:
1) the id of the edges on the path from v to u must be increasing (so that v passes through all nodes on the path and eventually comes to u)
2) and the max edge id on the path must be less than the curr query id (otherwise the max edge will never exist during the time of the query, so u and v will never be connected during the time of the query)

rewriting the conditions by including the lca so that it's easier to compute:

v -> u = v -> lca + lca -> u

v -> lca = inc
u -> lca = dec
max(v->lca) < min(u->lca)
max(v->u) < id

type C queries:
centroid decomp

*/
 
const int MOD = 1e9 + 7;
const int N = 1.2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
 
 template<typename T>
struct fenwick {
    int siz;
    vector<T> tree;

    fenwick(){

    }

    fenwick(int n) {
        siz = n;
        tree = vector<T>(n + 1);
    }

    int lsb(int x) {
        return x & -x;
    }

    void build(vector<T> &a, int n) {
        for (int i = 1; i <= n; ++i) {
            int par = i + lsb(i);
            tree[i] += a[i];

            if (par <= siz) {
                tree[par] += tree[i];
            }
        }
    }

    void pupd(int i, T v) {
        i++;

        while (i <= siz) {
            tree[i] += v;
            i += lsb(i);
        }
    }

    T sum(int i) {
        i++;

        T res = 0;

        while (i) {
            res += tree[i];
            i -= lsb(i);
        }

        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }
};

vector<pii> adj[N];
 
struct lca_algo {
    // LCA template (for graphs with 1-based indexing)
 
    int LOG = 1;
    vector<int> depth;
    vector<vector<int>> up;
    vector<vector<int>> mn, mx, inc, dec;
 
    lca_algo() {
 
    }
 
    lca_algo(int n) {
        lca_init(n);
    }
 
    void lca_init(int n) {
        while ((1 << LOG) < n) LOG++;
        up = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
        depth = vector<int>(n + 1);
        mn = vector<vector<int>>(n + 1, vector<int>(LOG, inf1));
        mx = vector<vector<int>>(n + 1, vector<int>(LOG, -inf1));
        inc = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
        dec = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
 
        lca_dfs(1, -1);
    }
 
    void lca_dfs(int node, int par) {
        for(auto [child, w] : adj[node]) {
            if (child == par) conts;
 
            depth[child] = depth[node] + 1;
 
            up[child][0] = node;
            rep1(j, LOG - 1) {
                up[child][j] = up[up[child][j - 1]][j - 1];
            }
 
            mn[child][0] = mx[child][0] = w;
            rep1(j,LOG-1){
                mn[child][j] = min(mn[child][j-1], mn[up[child][j-1]][j-1]);
                mx[child][j] = max(mx[child][j-1], mx[up[child][j-1]][j-1]);
            }
 
            inc[child][0] = dec[child][0] = 1;
            rep1(j,LOG-1){
                inc[child][j] = (inc[child][j-1] & inc[up[child][j-1]][j-1] & mx[child][j-1] < mn[up[child][j-1]][j-1]);
                dec[child][j] = (dec[child][j-1] & dec[up[child][j-1]][j-1] & mn[child][j-1] > mx[up[child][j-1]][j-1]);
            }
 
            lca_dfs(child, node);
        }
    }
 
    int lift(int u, int k) {
        rep(j, LOG) {
            if (k & (1 << j)) {
                u = up[u][j];
            }
        }
 
        return u;
    }
 
    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        u = lift(u, k);
 
        if (u == v) return u;
 
        rev(j, LOG - 1, 0) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
 
        u = up[u][0];
        return u;
    }
 
    array<int,4> get(int u, int lca){
        int k = depth[u] - depth[lca];
        array<int,4> curr = {inf1,-inf1,1,1};
 
        rep(j,LOG){
            if(!(k & (1 << j))) conts;
 
            // merge curr with up[u][j]
            array<int,4> curr_new;
            curr_new[0] = min(curr[0], mn[u][j]);
            curr_new[1] = max(curr[1], mx[u][j]);
            curr_new[2] = (curr[2] & inc[u][j] & curr[1] < mn[u][j]);
            curr_new[3] = (curr[3] & dec[u][j] & curr[0] > mx[u][j]);
 
            curr = curr_new;
            u = up[u][j];
        }
 
        assert(u == lca);
        return curr;
    }
 
    int get_dis(int u, int v) {
        int lca = query(u, v);
        return depth[u] + depth[v] - 2 * depth[lca];
    }

    bool is_inc(int u, int v, int t){
        // is the path from u to v increasing at time t?
        int lca = query(u,v);
 
        auto [mn1,mx1,inc1,dec1] = get(u,lca);
        auto [mn2,mx2,inc2,dec2] = get(v,lca);
 
        if(inc1 and dec2 and mx1 < mn2 and max(mx1,mx2) < t){
            return true;
        }
        else{
            return false;
        } 
    }

    array<int,4> path_data(int u, int v){
        // returns {is_inc, is_dec, mn, mx}
        int lca = query(u,v);
 
        auto [mn1,mx1,inc1,dec1] = get(u,lca);
        auto [mn2,mx2,inc2,dec2] = get(v,lca);
    
        int is_inc = 0, is_dec = 0;

        if(inc1 and dec2 and mx1 < mn2){
            is_inc = 1;
        }

        if(dec1 and inc2 and mn1 > mx2){
            is_dec = 1;
        }

        int mn = min(mn1,mn2);
        int mx = max(mx1,mx2);

        return {is_inc, is_dec, mn, mx};
    }
};

vector<int> subsiz(N), par(N,-1);
vector<bool> rem(N);

int get_siz(int u, int p){
    subsiz[u] = 1;
    for(auto [v, id] : adj[u]){
        if(rem[v] or v == p) conts;
        subsiz[u] += get_siz(v,u);
    }
    return subsiz[u];
}

int get_centroid(int u, int p, int nodes){
    for(auto [v, id] : adj[u]){
        if(rem[v] or v == p) conts;
        if(subsiz[v] > nodes / 2){
            return get_centroid(v,u,nodes);
        }
    }
    return u;
}

void build(int u, int p){
    int nodes = get_siz(u,-1);
    int centroid = get_centroid(u,-1,nodes);

    rem[centroid] = 1;
    par[centroid] = p;

    for(auto [v, id] : adj[centroid]){
        if(rem[v]) conts;
        build(v,centroid);
    }
}

vector<int> adj_ids[N];
fenwick<int> fenw[N];

void solve(int test_case)
{
    int n,k; cin >> n >> k;
    vector<array<int,3>> queries(n+k+5);
 
    rep1(id,n+k-1){
        char ch; cin >> ch;
        int t = 0;
        if(ch == 'S') t = 1;
        else if(ch == 'Q') t = 2;
        else t = 3;
    
        if(t <= 2){
            int u,v; cin >> u >> v;
            queries[id] = {t, u, v};        
            
            if(t == 1){
                adj[u].pb({v,id});
                adj[v].pb({u,id});

                adj_ids[u].pb(id);
                adj_ids[v].pb(id);
            }   
        }
        else{
            int u; cin >> u;
            queries[id] = {t, u};
        }
    }
    
    rep1(i,n){
        adj_ids[i].pb(-inf1);
        adj_ids[i].pb(inf1);
        sort(all(adj_ids[i]));
        int siz = sz(adj_ids[i]);
        fenw[i] = fenwick<int>(siz);
    }

    lca_algo LCA(n);
    build(1,-1);

    vector<pii> here[n+k+5];
    vector<array<int,4>> vals[n+5];

    rep1(u,n){
        for(int centroid = u; centroid != -1; centroid = par[centroid]){
            auto [is_inc, is_dec, mn, mx] = LCA.path_data(u,centroid);
            auto &ids = adj_ids[centroid];
            int mx_ind = lower_bound(all(ids),mx) - ids.begin();
            vals[u].pb({centroid, is_inc, mx, mx_ind});

            if(!is_dec) conts;

            amax(mx, 1);
            mn = lower_bound(all(ids),mn) - ids.begin();
            here[mx].pb({centroid,mn});
        }
    }

    rep1(id,n+k-1){
        auto [t,u,v] = queries[id];

        for(auto [centroid, pos] : here[id]){
            fenw[centroid].pupd(pos,1);
        }

        if(t == 1) conts;

        if(t == 2){
            if(LCA.is_inc(v,u,id)) yes;
            else no;
            conts;
        }

        int ans = 0;

        for(auto [centroid, is_inc, mx, mx_ind] : vals[u]){
            if(!is_inc) conts;
            if(mx > id) conts;

            int siz = sz(adj_ids[centroid]);
            ans += fenw[centroid].query(mx_ind+1, siz-1);
        }

        cout << ans << endl;
    }
}
 
int main()
{
    fastio;
 
    int t = 1;
    // cin >> t;
 
    rep1(i, t) {
        solve(i);
    }
 
    return 0;
}

Compilation message

servers.cpp: In member function 'void lca_algo::lca_dfs(int, int)':
servers.cpp:189:94: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  189 |                 inc[child][j] = (inc[child][j-1] & inc[up[child][j-1]][j-1] & mx[child][j-1] < mn[up[child][j-1]][j-1]);
servers.cpp:190:94: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  190 |                 dec[child][j] = (dec[child][j-1] & dec[up[child][j-1]][j-1] & mn[child][j-1] > mx[up[child][j-1]][j-1]);
servers.cpp: In member function 'std::array<int, 4> lca_algo::get(int, int)':
servers.cpp:236:58: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  236 |             curr_new[2] = (curr[2] & inc[u][j] & curr[1] < mn[u][j]);
servers.cpp:237:58: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  237 |             curr_new[3] = (curr[3] & dec[u][j] & curr[0] > mx[u][j]);

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15180 KB Output is correct
2 Correct 70 ms 18372 KB Output is correct
3 Correct 59 ms 18208 KB Output is correct
4 Correct 89 ms 18828 KB Output is correct
5 Correct 72 ms 18776 KB Output is correct
6 Correct 50 ms 17996 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15180 KB Output is correct
2 Correct 70 ms 18372 KB Output is correct
3 Correct 59 ms 18208 KB Output is correct
4 Correct 89 ms 18828 KB Output is correct
5 Correct 72 ms 18776 KB Output is correct
6 Correct 50 ms 17996 KB Output is correct
7 Correct 35 ms 15220 KB Output is correct
8 Correct 64 ms 18280 KB Output is correct
9 Correct 55 ms 18252 KB Output is correct
10 Correct 95 ms 18736 KB Output is correct
11 Correct 85 ms 18720 KB Output is correct
12 Correct 48 ms 18132 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15308 KB Output is correct
2 Correct 514 ms 107336 KB Output is correct
3 Correct 483 ms 107296 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15308 KB Output is correct
2 Correct 514 ms 107336 KB Output is correct
3 Correct 483 ms 107296 KB Output is correct
4 Correct 32 ms 15300 KB Output is correct
5 Correct 501 ms 107396 KB Output is correct
6 Correct 400 ms 107672 KB Output is correct
7 Correct 420 ms 107592 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15272 KB Output is correct
2 Correct 972 ms 148416 KB Output is correct
3 Correct 929 ms 148360 KB Output is correct
4 Correct 964 ms 156528 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15272 KB Output is correct
2 Correct 972 ms 148416 KB Output is correct
3 Correct 929 ms 148360 KB Output is correct
4 Correct 964 ms 156528 KB Output is correct
5 Correct 38 ms 15168 KB Output is correct
6 Correct 992 ms 148296 KB Output is correct
7 Correct 903 ms 155968 KB Output is correct
8 Correct 970 ms 148216 KB Output is correct
9 Correct 954 ms 148264 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15188 KB Output is correct
2 Correct 613 ms 139632 KB Output is correct
3 Correct 722 ms 134132 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15188 KB Output is correct
2 Correct 613 ms 139632 KB Output is correct
3 Correct 722 ms 134132 KB Output is correct
4 Correct 36 ms 15172 KB Output is correct
5 Correct 621 ms 139556 KB Output is correct
6 Correct 720 ms 133876 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15212 KB Output is correct
2 Correct 990 ms 148304 KB Output is correct
3 Correct 1031 ms 148408 KB Output is correct
4 Correct 1006 ms 156532 KB Output is correct
5 Correct 32 ms 15172 KB Output is correct
6 Correct 641 ms 139488 KB Output is correct
7 Correct 726 ms 134020 KB Output is correct
8 Correct 1181 ms 133636 KB Output is correct
9 Correct 1193 ms 133836 KB Output is correct
10 Correct 2592 ms 143708 KB Output is correct
11 Correct 2984 ms 143720 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15212 KB Output is correct
2 Correct 990 ms 148304 KB Output is correct
3 Correct 1031 ms 148408 KB Output is correct
4 Correct 1006 ms 156532 KB Output is correct
5 Correct 32 ms 15172 KB Output is correct
6 Correct 641 ms 139488 KB Output is correct
7 Correct 726 ms 134020 KB Output is correct
8 Correct 1181 ms 133636 KB Output is correct
9 Correct 1193 ms 133836 KB Output is correct
10 Correct 2592 ms 143708 KB Output is correct
11 Correct 2984 ms 143720 KB Output is correct
12 Correct 41 ms 15516 KB Output is correct
13 Correct 1083 ms 148508 KB Output is correct
14 Correct 1012 ms 156180 KB Output is correct
15 Correct 1043 ms 148412 KB Output is correct
16 Correct 1049 ms 148368 KB Output is correct
17 Correct 37 ms 15432 KB Output is correct
18 Correct 665 ms 139772 KB Output is correct
19 Correct 810 ms 134040 KB Output is correct
20 Correct 1351 ms 133880 KB Output is correct
21 Correct 1265 ms 133840 KB Output is correct
22 Correct 2717 ms 143992 KB Output is correct
23 Correct 2893 ms 147568 KB Output is correct
24 Correct 2822 ms 146516 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15420 KB Output is correct
2 Correct 72 ms 18684 KB Output is correct
3 Correct 53 ms 18628 KB Output is correct
4 Correct 95 ms 19100 KB Output is correct
5 Correct 81 ms 19148 KB Output is correct
6 Correct 54 ms 18384 KB Output is correct
7 Correct 34 ms 15480 KB Output is correct
8 Correct 551 ms 107704 KB Output is correct
9 Correct 520 ms 107780 KB Output is correct
10 Correct 35 ms 15520 KB Output is correct
11 Correct 980 ms 148840 KB Output is correct
12 Correct 984 ms 148828 KB Output is correct
13 Correct 1027 ms 157044 KB Output is correct
14 Correct 39 ms 15572 KB Output is correct
15 Correct 638 ms 139960 KB Output is correct
16 Correct 764 ms 134408 KB Output is correct
17 Correct 1303 ms 134024 KB Output is correct
18 Correct 1234 ms 134136 KB Output is correct
19 Correct 2799 ms 144308 KB Output is correct
20 Correct 2934 ms 144112 KB Output is correct
21 Correct 579 ms 109876 KB Output is correct
22 Correct 569 ms 110528 KB Output is correct
23 Correct 765 ms 121316 KB Output is correct
24 Correct 760 ms 121572 KB Output is correct
25 Correct 1882 ms 128976 KB Output is correct
26 Correct 1050 ms 129068 KB Output is correct
27 Correct 965 ms 128804 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15420 KB Output is correct
2 Correct 72 ms 18684 KB Output is correct
3 Correct 53 ms 18628 KB Output is correct
4 Correct 95 ms 19100 KB Output is correct
5 Correct 81 ms 19148 KB Output is correct
6 Correct 54 ms 18384 KB Output is correct
7 Correct 34 ms 15480 KB Output is correct
8 Correct 551 ms 107704 KB Output is correct
9 Correct 520 ms 107780 KB Output is correct
10 Correct 35 ms 15520 KB Output is correct
11 Correct 980 ms 148840 KB Output is correct
12 Correct 984 ms 148828 KB Output is correct
13 Correct 1027 ms 157044 KB Output is correct
14 Correct 39 ms 15572 KB Output is correct
15 Correct 638 ms 139960 KB Output is correct
16 Correct 764 ms 134408 KB Output is correct
17 Correct 1303 ms 134024 KB Output is correct
18 Correct 1234 ms 134136 KB Output is correct
19 Correct 2799 ms 144308 KB Output is correct
20 Correct 2934 ms 144112 KB Output is correct
21 Correct 579 ms 109876 KB Output is correct
22 Correct 569 ms 110528 KB Output is correct
23 Correct 765 ms 121316 KB Output is correct
24 Correct 760 ms 121572 KB Output is correct
25 Correct 1882 ms 128976 KB Output is correct
26 Correct 1050 ms 129068 KB Output is correct
27 Correct 965 ms 128804 KB Output is correct
28 Correct 38 ms 15436 KB Output is correct
29 Correct 63 ms 18780 KB Output is correct
30 Correct 50 ms 18760 KB Output is correct
31 Correct 90 ms 19264 KB Output is correct
32 Correct 64 ms 19244 KB Output is correct
33 Correct 46 ms 18624 KB Output is correct
34 Correct 45 ms 15776 KB Output is correct
35 Correct 512 ms 107888 KB Output is correct
36 Correct 417 ms 108168 KB Output is correct
37 Correct 428 ms 107908 KB Output is correct
38 Correct 35 ms 15560 KB Output is correct
39 Correct 1018 ms 148680 KB Output is correct
40 Correct 950 ms 156356 KB Output is correct
41 Correct 1008 ms 148616 KB Output is correct
42 Correct 1018 ms 148640 KB Output is correct
43 Correct 35 ms 15620 KB Output is correct
44 Correct 615 ms 139900 KB Output is correct
45 Correct 713 ms 134332 KB Output is correct
46 Correct 1264 ms 134048 KB Output is correct
47 Correct 1353 ms 133996 KB Output is correct
48 Correct 2755 ms 143968 KB Output is correct
49 Correct 3017 ms 150104 KB Output is correct
50 Correct 2909 ms 149468 KB Output is correct
51 Correct 463 ms 112396 KB Output is correct
52 Correct 415 ms 110188 KB Output is correct
53 Correct 406 ms 109832 KB Output is correct
54 Correct 410 ms 110472 KB Output is correct
55 Correct 458 ms 112140 KB Output is correct
56 Correct 688 ms 124688 KB Output is correct
57 Correct 1854 ms 131252 KB Output is correct
58 Correct 1042 ms 132320 KB Output is correct
59 Correct 1022 ms 131288 KB Output is correct