oj.uz

답안 #995651

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
995651 2024-06-09T15:19:41 Z vladilius Inside information (BOI21_servers) C++17
7.5 / 100
 88 ms 27576 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 = q + 1;
        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;
            }
        }
        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 (!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
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 2136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 2136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2136 KB Output is correct
2 Correct 70 ms 16844 KB Output is correct
3 Correct 66 ms 16752 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2136 KB Output is correct
2 Correct 70 ms 16844 KB Output is correct
3 Correct 66 ms 16752 KB Output is correct
4 Incorrect 17 ms 2136 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2140 KB Output is correct
2 Correct 75 ms 27500 KB Output is correct
3 Correct 80 ms 27532 KB Output is correct
4 Correct 64 ms 27576 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2140 KB Output is correct
2 Correct 75 ms 27500 KB Output is correct
3 Correct 80 ms 27532 KB Output is correct
4 Correct 64 ms 27576 KB Output is correct
5 Incorrect 16 ms 2884 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 2128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 2128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 2136 KB Output is correct
2 Correct 88 ms 27520 KB Output is correct
3 Correct 76 ms 27476 KB Output is correct
4 Correct 83 ms 27480 KB Output is correct
5 Incorrect 21 ms 2908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 2136 KB Output is correct
2 Correct 88 ms 27520 KB Output is correct
3 Correct 76 ms 27476 KB Output is correct
4 Correct 83 ms 27480 KB Output is correct
5 Incorrect 21 ms 2908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 2136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 2136 KB Output isn't correct
2 Halted 0 ms 0 KB -