Submission #995650

#	Time	Username	Problem	Language	Result	Execution time	Memory
995650		vladilius	Inside information (BOI21_servers)	C++17	15 / 100	3586 ms	31912 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

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 (stderr)

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