oj.uz

Submission #995657

# Submission time Handle Problem Language Result Execution time Memory
995657 2024-06-09T15:32:07 Z vladilius Inside information (BOI21_servers) C++17
50 / 100
 89 ms 27616 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert

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

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);
    
    /*
    vector<int> inv(n + 1);
    for (int i = 1; i <= n; i++) inv[pos[i]] = i;
     */

    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 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);
    };
    
    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);
    };
    
    auto check = [&](int x, int y){
        int a = lca(x, y), pre = 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 0;
                x = p[head[x]];
                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 0;
                if (l <= r) pre = 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 0;
            pre = f[r];
        }
        return 1;
    };
    
    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) ? "yes" : "no")<<"\n";
            // b -> a
        }
        else {
            cout<<0<<"\n";
        }
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2136 KB Output is correct
2 Correct 25 ms 2644 KB Output is correct
3 Correct 25 ms 2640 KB Output is correct
4 Correct 22 ms 2652 KB Output is correct
5 Correct 21 ms 2908 KB Output is correct
6 Correct 23 ms 2592 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2136 KB Output is correct
2 Correct 25 ms 2644 KB Output is correct
3 Correct 25 ms 2640 KB Output is correct
4 Correct 22 ms 2652 KB Output is correct
5 Correct 21 ms 2908 KB Output is correct
6 Correct 23 ms 2592 KB Output is correct
7 Incorrect 17 ms 2140 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2140 KB Output is correct
2 Correct 60 ms 16848 KB Output is correct
3 Correct 65 ms 16844 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2140 KB Output is correct
2 Correct 60 ms 16848 KB Output is correct
3 Correct 65 ms 16844 KB Output is correct
4 Incorrect 16 ms 2140 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2136 KB Output is correct
2 Correct 75 ms 27472 KB Output is correct
3 Correct 87 ms 27616 KB Output is correct
4 Correct 61 ms 27472 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2136 KB Output is correct
2 Correct 75 ms 27472 KB Output is correct
3 Correct 87 ms 27616 KB Output is correct
4 Correct 61 ms 27472 KB Output is correct
5 Incorrect 16 ms 2136 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2244 KB Output is correct
2 Correct 88 ms 16312 KB Output is correct
3 Correct 76 ms 16340 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2244 KB Output is correct
2 Correct 88 ms 16312 KB Output is correct
3 Correct 76 ms 16340 KB Output is correct
4 Incorrect 17 ms 2204 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2136 KB Output is correct
2 Correct 79 ms 27488 KB Output is correct
3 Correct 85 ms 27472 KB Output is correct
4 Correct 63 ms 27476 KB Output is correct
5 Correct 17 ms 2140 KB Output is correct
6 Correct 86 ms 19552 KB Output is correct
7 Correct 80 ms 19492 KB Output is correct
8 Correct 85 ms 20052 KB Output is correct
9 Correct 84 ms 20128 KB Output is correct
10 Correct 76 ms 23892 KB Output is correct
11 Correct 74 ms 22868 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2136 KB Output is correct
2 Correct 79 ms 27488 KB Output is correct
3 Correct 85 ms 27472 KB Output is correct
4 Correct 63 ms 27476 KB Output is correct
5 Correct 17 ms 2140 KB Output is correct
6 Correct 86 ms 19552 KB Output is correct
7 Correct 80 ms 19492 KB Output is correct
8 Correct 85 ms 20052 KB Output is correct
9 Correct 84 ms 20128 KB Output is correct
10 Correct 76 ms 23892 KB Output is correct
11 Correct 74 ms 22868 KB Output is correct
12 Incorrect 16 ms 2908 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2140 KB Output is correct
2 Correct 26 ms 2520 KB Output is correct
3 Correct 23 ms 2652 KB Output is correct
4 Correct 22 ms 2652 KB Output is correct
5 Correct 21 ms 2912 KB Output is correct
6 Correct 23 ms 2664 KB Output is correct
7 Correct 16 ms 2140 KB Output is correct
8 Correct 59 ms 16844 KB Output is correct
9 Correct 65 ms 16844 KB Output is correct
10 Correct 16 ms 2140 KB Output is correct
11 Correct 76 ms 27472 KB Output is correct
12 Correct 87 ms 27476 KB Output is correct
13 Correct 62 ms 27476 KB Output is correct
14 Correct 17 ms 2908 KB Output is correct
15 Correct 89 ms 19620 KB Output is correct
16 Correct 78 ms 19540 KB Output is correct
17 Correct 86 ms 20308 KB Output is correct
18 Correct 88 ms 20172 KB Output is correct
19 Correct 74 ms 23928 KB Output is correct
20 Correct 77 ms 23096 KB Output is correct
21 Correct 75 ms 20024 KB Output is correct
22 Correct 68 ms 20188 KB Output is correct
23 Correct 75 ms 20212 KB Output is correct
24 Correct 73 ms 20252 KB Output is correct
25 Correct 72 ms 22960 KB Output is correct
26 Correct 76 ms 19812 KB Output is correct
27 Correct 77 ms 19796 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2140 KB Output is correct
2 Correct 26 ms 2520 KB Output is correct
3 Correct 23 ms 2652 KB Output is correct
4 Correct 22 ms 2652 KB Output is correct
5 Correct 21 ms 2912 KB Output is correct
6 Correct 23 ms 2664 KB Output is correct
7 Correct 16 ms 2140 KB Output is correct
8 Correct 59 ms 16844 KB Output is correct
9 Correct 65 ms 16844 KB Output is correct
10 Correct 16 ms 2140 KB Output is correct
11 Correct 76 ms 27472 KB Output is correct
12 Correct 87 ms 27476 KB Output is correct
13 Correct 62 ms 27476 KB Output is correct
14 Correct 17 ms 2908 KB Output is correct
15 Correct 89 ms 19620 KB Output is correct
16 Correct 78 ms 19540 KB Output is correct
17 Correct 86 ms 20308 KB Output is correct
18 Correct 88 ms 20172 KB Output is correct
19 Correct 74 ms 23928 KB Output is correct
20 Correct 77 ms 23096 KB Output is correct
21 Correct 75 ms 20024 KB Output is correct
22 Correct 68 ms 20188 KB Output is correct
23 Correct 75 ms 20212 KB Output is correct
24 Correct 73 ms 20252 KB Output is correct
25 Correct 72 ms 22960 KB Output is correct
26 Correct 76 ms 19812 KB Output is correct
27 Correct 77 ms 19796 KB Output is correct
28 Incorrect 17 ms 2908 KB Extra information in the output file
29 Halted 0 ms 0 KB -