Submission #996182

#	Time	Username	Problem	Language	Result	Execution time	Memory
996182		vladilius	Inside information (BOI21_servers)	C++17	80 / 100	3567 ms	81100 KiB

servers

#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
#define arr3 array<int, 3>

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{
    vector<int> a;
    void add(int x){
        a.pb(x);
    }
    int get(int x){
        int out = 1;
        for (int i: a) out += (i > x);
        return out;
    }
};

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
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5