oj.uz

Submission #995650

# Submission time Handle Problem Language Result Execution time Memory
995650 2024-06-09T15:05:58 Z vladilius Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 31912 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);
    
    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){
        f[pr(a, b)] = 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 - 1, v);
        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 = q + 1;
        while (true){
            // xl > ... > xr
            if (d[head[x]] > d[a]){
                int l = pos[head[x]], r = pos[x];
                if (T2.q(r) > l || f[l] > pre) return 0;
                x = p[head[x]];
                pre = f[l];
            }
            else {
                int l = pos[a] + 1, r = pos[x];
                if (l <= r && (T2.q(r) > l || f[l] > pre)) return 0;
                if (l <= r) pre = f[l];
                break;
            }
        }
        if (pre > q) pre = 0;
        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 (T1.q(l) < r || f[r] < pre) return 0;
            pre = f[r];
        }
        return 1;
    };
     */
    auto check = [&](int x, int y){
        vector<int> v1, v2;
        int a = lca(x, y);
        while (x != a){
            if (!f[x]) return 0;
            v1.pb(f[x]);
            x = p[x];
        }
        while (y != a){
            if (!f[y]) return 0;
            v2.pb(f[y]);
            y = p[y];
        }
        reverse(v2.begin(), v2.end());
        for (int i: v2) v1.pb(i);
        for (int i = 0; i + 1 < v1.size(); i++){
            if (v1[i] > v1[i + 1]){
                return 0;
            }
        }
        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";
        }
    }
}

Compilation message

servers.cpp: In lambda function:
servers.cpp:183:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |         for (int i = 0; i + 1 < v1.size(); i++){
      |                         ~~~~~~^~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2140 KB Output is correct
2 Correct 32 ms 3932 KB Output is correct
3 Correct 34 ms 3980 KB Output is correct
4 Correct 26 ms 4180 KB Output is correct
5 Correct 585 ms 4464 KB Output is correct
6 Correct 26 ms 3920 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2140 KB Output is correct
2 Correct 32 ms 3932 KB Output is correct
3 Correct 34 ms 3980 KB Output is correct
4 Correct 26 ms 4180 KB Output is correct
5 Correct 585 ms 4464 KB Output is correct
6 Correct 26 ms 3920 KB Output is correct
7 Incorrect 22 ms 2908 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 18 ms 2140 KB Output is correct
2 Correct 62 ms 19660 KB Output is correct
3 Correct 63 ms 19508 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2140 KB Output is correct
2 Correct 62 ms 19660 KB Output is correct
3 Correct 63 ms 19508 KB Output is correct
4 Incorrect 18 ms 2904 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2140 KB Output is correct
2 Correct 84 ms 31908 KB Output is correct
3 Correct 82 ms 31576 KB Output is correct
4 Execution timed out 3547 ms 31444 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2140 KB Output is correct
2 Correct 84 ms 31908 KB Output is correct
3 Correct 82 ms 31576 KB Output is correct
4 Execution timed out 3547 ms 31444 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2136 KB Output is correct
2 Correct 94 ms 19480 KB Output is correct
3 Correct 68 ms 19540 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2136 KB Output is correct
2 Correct 94 ms 19480 KB Output is correct
3 Correct 68 ms 19540 KB Output is correct
4 Incorrect 21 ms 3008 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2140 KB Output is correct
2 Correct 79 ms 31832 KB Output is correct
3 Correct 79 ms 31708 KB Output is correct
4 Execution timed out 3586 ms 31548 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2140 KB Output is correct
2 Correct 79 ms 31832 KB Output is correct
3 Correct 79 ms 31708 KB Output is correct
4 Execution timed out 3586 ms 31548 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2140 KB Output is correct
2 Correct 31 ms 4040 KB Output is correct
3 Correct 28 ms 3932 KB Output is correct
4 Correct 27 ms 4180 KB Output is correct
5 Correct 609 ms 4380 KB Output is correct
6 Correct 25 ms 3932 KB Output is correct
7 Correct 17 ms 2908 KB Output is correct
8 Correct 63 ms 19664 KB Output is correct
9 Correct 63 ms 19660 KB Output is correct
10 Correct 21 ms 2908 KB Output is correct
11 Correct 81 ms 31912 KB Output is correct
12 Correct 87 ms 31576 KB Output is correct
13 Execution timed out 3543 ms 31424 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2140 KB Output is correct
2 Correct 31 ms 4040 KB Output is correct
3 Correct 28 ms 3932 KB Output is correct
4 Correct 27 ms 4180 KB Output is correct
5 Correct 609 ms 4380 KB Output is correct
6 Correct 25 ms 3932 KB Output is correct
7 Correct 17 ms 2908 KB Output is correct
8 Correct 63 ms 19664 KB Output is correct
9 Correct 63 ms 19660 KB Output is correct
10 Correct 21 ms 2908 KB Output is correct
11 Correct 81 ms 31912 KB Output is correct
12 Correct 87 ms 31576 KB Output is correct
13 Execution timed out 3543 ms 31424 KB Time limit exceeded
14 Halted 0 ms 0 KB -