oj.uz

Submission #996194

# Submission time Handle Problem Language Result Execution time Memory
996194 2024-06-10T08:39:05 Z vladilius Inside information (BOI21_servers) C++17
100 / 100
 1756 ms 125024 KB 
#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;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
using ordered_set = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;

struct dsu{
    vector<int> sz, m, p;
    int n; bool t;
    dsu(int ns, bool ts){
        n = ns; t = ts;
        p.resize(n + 1);
        sz.resize(n + 1);
        m.resize(n + 1);
        for (int i = 1; i <= n; i++){
            p[i] = m[i] = i;
            sz[i] = 1;
        }
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    int f(int x, int y){
        if (t) return max(x, y);
        return min(x, y);
    }
    int q(int v){
        return m[get(v)];
    }
    void unite(int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
        m[y] = f(m[y], m[x]);
    }
};

struct NC{
    ordered_set a;
    void add(int x){
        a.ins(x);
    }
    int get(int x){
        return 1 + a.size() - a.order_of_key(x + 1);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    struct query{
        char t;
        int x, y;
    };
    
    int n, q; cin>>n>>q;
    q += (n - 1);
    
    vector<query> qs(q + 1);
    vector<int> g[n + 1];
    for (int i = 1; i <= q; i++){
        cin>>qs[i].t>>qs[i].x;
        if (qs[i].t != 'C') cin>>qs[i].y;
        if (qs[i].t == 'S'){
            g[qs[i].x].pb(qs[i].y);
            g[qs[i].y].pb(qs[i].x);
        }
    }
    
    vector<int> sz(n + 1), d(n + 1), h(n + 1), p(n + 1);
    function<void(int, int)> dfs = [&](int v, int pr){
        p[v] = pr;
        sz[v] = 1;
        for (int i: g[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            dfs(i, v);
            if (sz[i] > sz[h[v]]){
                h[v] = i;
            }
            sz[v] += sz[i];
        }
    };
    dfs(1, 0);
    
    vector<int> head(n + 1), pos(n + 1);
    int timer = 0;
    function<void(int, int)> dfs_hld = [&](int v, int k){
        head[v] = k;
        pos[v] = ++timer;
        if (!h[v]) return;
        dfs_hld(h[v], k);
        for (int i: g[v]){
            if (pos[i]) continue;
            dfs_hld(i, i);
        }
    };
    dfs_hld(1, 1);

    auto pr = [&](int a, int b){
        return (d[a] > d[b]) ? a : b;
    };
    
    vector<int> f(n + 1);
    dsu T1(n, 1), T2(n, 0);
    
    auto lca = [&](int x, int y){
        while (head[x] != head[y]){
            if (d[head[x]] > d[head[y]]){
                swap(x, y);
            }
            y = p[head[y]];
        }
        return ((d[x] > d[y]) ? y : x);
    };
    
    const arr3 zr = {0, 0, 0};
    
    auto check = [&](int x, int y){
        int a = lca(x, y), pre = 0, mini = q + 1, maxi = 0;
        while (true){
            // xl > ... > xr
            if (d[head[x]] > d[a]){
                int l = pos[head[x]], r = pos[x];
                if (!f[r] || T2.q(r) > l || f[r] < pre) return zr;
                x = p[head[x]];
                mini = min(mini, f[r]);
                maxi = max(maxi, f[l]);
                pre = f[l];
            }
            else {
                int l = pos[a] + 1, r = pos[x];
                if (l <= r && (!f[r] || T2.q(r) > l || f[r] < pre)) return zr;
                if (l <= r){
                    pre = f[l];
                    mini = min(mini, f[r]);
                    maxi = max(maxi, f[l]);
                }
                break;
            }
        }
        vector<pii> all;
        while (true){
            // xl < ... < xr
            if (d[head[y]] > d[a]){
                int l = pos[head[y]], r = pos[y];
                all.pb({l, r});
                y = p[head[y]];
            }
            else {
                int l = pos[a] + 1, r = pos[y];
                if (l <= r) all.pb({l, r});
                break;
            }
        }
        reverse(all.begin(), all.end());
        for (auto [l, r]: all){
            if (!f[l] || T1.q(l) < r || f[l] < pre) return zr;
            mini = min(mini, f[l]);
            maxi = max(maxi, f[r]);
            pre = f[r];
        }
        arr3 ret = {1, mini, maxi};
        return ret;
    };
    
    // Arvid's Decomposition
    vector<bool> used(n + 1);
    function<void(int, int)> fill_sz = [&](int v, int pr){
        sz[v] = 1;
        for (int i: g[v]){
            if (i == pr || used[i]) continue;
            fill_sz(i, v);
            sz[v] += sz[i];
        }
    };
    function<int(int, int, int&)> find = [&](int v, int pr, int& S){
        for (int i: g[v]){
            if (i == pr || used[i]) continue;
            if (2 * sz[i] >= S) return find(i, v, S);
        }
        return v;
    };
    vector<int> par(n + 1), dd(n + 1);
    function<void(int, int, int)> arvid = [&](int v, int p, int s){
        fill_sz(v, 0);
        int k = find(v, 0, sz[v]);
        par[k] = p;
        dd[k] = s;
        used[k] = 1;
        for (int i: g[k]){
            if (used[i]) continue;
            arvid(i, k, s + 1);
        }
    };
    arvid(1, 0, 0);
    
    NC T[n + 1];
    map<int, bool> mp[n + 1];
    auto get = [&](int v){
        int t = par[v], out = T[v].get(0);
        while (t > 0){
            arr3 d = check(v, t);
            if (d[0]){
                out += T[t].get(d[2]);
            }
            t = par[t];
        }
        return out;
    };
    
    auto add = [&](int x){
        int t = par[x];
        while (t > 0){
            arr3 d = check(t, x);
            if (mp[t].find(x) == mp[t].end() && d[0]){
                mp[t][x] = 1;
                T[t].add(d[1]);
            }
            t = par[t];
        }
    };
    
    auto upd = [&](int a, int b, int i){
        int v = pos[pr(a, b)];
        f[v] = i;
        if (f[v - 1] && f[v - 1] < f[v]) T1.unite(v, v - 1);
        if (v != n && f[v] < f[v + 1]) T1.unite(v, v + 1);
        if (f[v - 1] > f[v]) T2.unite(v, v - 1);
        if (v != n && f[v + 1] && f[v] > f[v + 1]) T2.unite(v, v + 1);
        
        add(a); add(b);
    };
    
    for (int i = 1; i <= q; i++){
        if (qs[i].t == 'S'){
            upd(qs[i].x, qs[i].y, i);
        }
        else if (qs[i].t == 'Q'){
            int a = qs[i].x, b = qs[i].y;
            cout<<(check(b, a)[0] ? "yes" : "no")<<"\n";
        }
        else {
            cout<<get(qs[i].x)<<"\n";
        }
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2908 KB Output is correct
2 Correct 34 ms 4632 KB Output is correct
3 Correct 29 ms 4688 KB Output is correct
4 Correct 31 ms 4700 KB Output is correct
5 Correct 27 ms 4644 KB Output is correct
6 Correct 26 ms 4576 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2908 KB Output is correct
2 Correct 34 ms 4632 KB Output is correct
3 Correct 29 ms 4688 KB Output is correct
4 Correct 31 ms 4700 KB Output is correct
5 Correct 27 ms 4644 KB Output is correct
6 Correct 26 ms 4576 KB Output is correct
7 Correct 18 ms 2908 KB Output is correct
8 Correct 46 ms 4352 KB Output is correct
9 Correct 34 ms 4428 KB Output is correct
10 Correct 47 ms 4340 KB Output is correct
11 Correct 62 ms 4432 KB Output is correct
12 Correct 26 ms 4432 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 233 ms 45768 KB Output is correct
3 Correct 213 ms 45964 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 233 ms 45768 KB Output is correct
3 Correct 213 ms 45964 KB Output is correct
4 Correct 17 ms 2904 KB Output is correct
5 Correct 213 ms 45552 KB Output is correct
6 Correct 184 ms 45464 KB Output is correct
7 Correct 196 ms 46028 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2904 KB Output is correct
2 Correct 389 ms 51536 KB Output is correct
3 Correct 411 ms 51640 KB Output is correct
4 Correct 558 ms 124752 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2904 KB Output is correct
2 Correct 389 ms 51536 KB Output is correct
3 Correct 411 ms 51640 KB Output is correct
4 Correct 558 ms 124752 KB Output is correct
5 Correct 18 ms 2908 KB Output is correct
6 Correct 441 ms 51352 KB Output is correct
7 Correct 670 ms 120556 KB Output is correct
8 Correct 497 ms 50888 KB Output is correct
9 Correct 495 ms 50768 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 868 ms 111476 KB Output is correct
3 Correct 622 ms 53584 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 868 ms 111476 KB Output is correct
3 Correct 622 ms 53584 KB Output is correct
4 Correct 25 ms 2816 KB Output is correct
5 Correct 940 ms 111156 KB Output is correct
6 Correct 700 ms 53388 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2856 KB Output is correct
2 Correct 434 ms 51468 KB Output is correct
3 Correct 432 ms 51840 KB Output is correct
4 Correct 579 ms 125024 KB Output is correct
5 Correct 19 ms 2896 KB Output is correct
6 Correct 943 ms 111188 KB Output is correct
7 Correct 639 ms 53528 KB Output is correct
8 Correct 525 ms 52304 KB Output is correct
9 Correct 472 ms 52304 KB Output is correct
10 Correct 560 ms 78544 KB Output is correct
11 Correct 564 ms 78184 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2856 KB Output is correct
2 Correct 434 ms 51468 KB Output is correct
3 Correct 432 ms 51840 KB Output is correct
4 Correct 579 ms 125024 KB Output is correct
5 Correct 19 ms 2896 KB Output is correct
6 Correct 943 ms 111188 KB Output is correct
7 Correct 639 ms 53528 KB Output is correct
8 Correct 525 ms 52304 KB Output is correct
9 Correct 472 ms 52304 KB Output is correct
10 Correct 560 ms 78544 KB Output is correct
11 Correct 564 ms 78184 KB Output is correct
12 Correct 18 ms 2896 KB Output is correct
13 Correct 472 ms 51284 KB Output is correct
14 Correct 718 ms 120400 KB Output is correct
15 Correct 515 ms 51024 KB Output is correct
16 Correct 466 ms 50772 KB Output is correct
17 Correct 20 ms 2904 KB Output is correct
18 Correct 960 ms 111124 KB Output is correct
19 Correct 692 ms 53296 KB Output is correct
20 Correct 586 ms 52164 KB Output is correct
21 Correct 529 ms 52300 KB Output is correct
22 Correct 711 ms 77792 KB Output is correct
23 Correct 1538 ms 109652 KB Output is correct
24 Correct 1173 ms 100092 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 33 ms 4700 KB Output is correct
3 Correct 28 ms 4692 KB Output is correct
4 Correct 32 ms 4568 KB Output is correct
5 Correct 37 ms 4688 KB Output is correct
6 Correct 25 ms 4700 KB Output is correct
7 Correct 17 ms 2864 KB Output is correct
8 Correct 218 ms 45768 KB Output is correct
9 Correct 238 ms 45768 KB Output is correct
10 Correct 17 ms 2768 KB Output is correct
11 Correct 421 ms 51536 KB Output is correct
12 Correct 411 ms 51536 KB Output is correct
13 Correct 565 ms 124912 KB Output is correct
14 Correct 18 ms 2904 KB Output is correct
15 Correct 941 ms 111188 KB Output is correct
16 Correct 678 ms 53584 KB Output is correct
17 Correct 520 ms 52216 KB Output is correct
18 Correct 460 ms 52312 KB Output is correct
19 Correct 559 ms 78676 KB Output is correct
20 Correct 544 ms 78028 KB Output is correct
21 Correct 262 ms 49736 KB Output is correct
22 Correct 243 ms 48268 KB Output is correct
23 Correct 599 ms 52800 KB Output is correct
24 Correct 526 ms 53332 KB Output is correct
25 Correct 411 ms 47568 KB Output is correct
26 Correct 379 ms 47524 KB Output is correct
27 Correct 387 ms 46952 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 33 ms 4700 KB Output is correct
3 Correct 28 ms 4692 KB Output is correct
4 Correct 32 ms 4568 KB Output is correct
5 Correct 37 ms 4688 KB Output is correct
6 Correct 25 ms 4700 KB Output is correct
7 Correct 17 ms 2864 KB Output is correct
8 Correct 218 ms 45768 KB Output is correct
9 Correct 238 ms 45768 KB Output is correct
10 Correct 17 ms 2768 KB Output is correct
11 Correct 421 ms 51536 KB Output is correct
12 Correct 411 ms 51536 KB Output is correct
13 Correct 565 ms 124912 KB Output is correct
14 Correct 18 ms 2904 KB Output is correct
15 Correct 941 ms 111188 KB Output is correct
16 Correct 678 ms 53584 KB Output is correct
17 Correct 520 ms 52216 KB Output is correct
18 Correct 460 ms 52312 KB Output is correct
19 Correct 559 ms 78676 KB Output is correct
20 Correct 544 ms 78028 KB Output is correct
21 Correct 262 ms 49736 KB Output is correct
22 Correct 243 ms 48268 KB Output is correct
23 Correct 599 ms 52800 KB Output is correct
24 Correct 526 ms 53332 KB Output is correct
25 Correct 411 ms 47568 KB Output is correct
26 Correct 379 ms 47524 KB Output is correct
27 Correct 387 ms 46952 KB Output is correct
28 Correct 20 ms 2896 KB Output is correct
29 Correct 51 ms 4348 KB Output is correct
30 Correct 38 ms 4564 KB Output is correct
31 Correct 48 ms 4296 KB Output is correct
32 Correct 45 ms 4436 KB Output is correct
33 Correct 32 ms 4264 KB Output is correct
34 Correct 19 ms 2896 KB Output is correct
35 Correct 248 ms 45504 KB Output is correct
36 Correct 230 ms 45260 KB Output is correct
37 Correct 198 ms 46096 KB Output is correct
38 Correct 18 ms 2916 KB Output is correct
39 Correct 488 ms 52308 KB Output is correct
40 Correct 741 ms 121756 KB Output is correct
41 Correct 492 ms 52028 KB Output is correct
42 Correct 602 ms 52096 KB Output is correct
43 Correct 18 ms 2908 KB Output is correct
44 Correct 988 ms 112360 KB Output is correct
45 Correct 754 ms 54372 KB Output is correct
46 Correct 705 ms 53336 KB Output is correct
47 Correct 588 ms 53388 KB Output is correct
48 Correct 707 ms 78792 KB Output is correct
49 Correct 1756 ms 110936 KB Output is correct
50 Correct 1173 ms 101460 KB Output is correct
51 Correct 245 ms 52300 KB Output is correct
52 Correct 169 ms 47056 KB Output is correct
53 Correct 178 ms 46540 KB Output is correct
54 Correct 178 ms 47072 KB Output is correct
55 Correct 195 ms 47180 KB Output is correct
56 Correct 506 ms 54628 KB Output is correct
57 Correct 394 ms 48776 KB Output is correct
58 Correct 531 ms 49004 KB Output is correct
59 Correct 335 ms 48212 KB Output is correct