제출 #401765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401765		gevacrt	Inside information (BOI21_servers)	C++17	50 / 100	1955 ms	137184 KiB

servers

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

const int MAXN = 12e4+10;
vvi adj(MAXN); vi depth(MAXN);

namespace DSU {
    vi par(MAXN), sz(MAXN);
    void init(){
        for(int x = 0; x < MAXN; x++)
            par[x] = x, sz[x] = 1;
    }
    
    int parent(int x){
        if(par[x] == x) return x;
        return par[x] = parent(par[x]);
    }

    void merge(int x, int y){
        x = parent(x), y = parent(y);
        if(x == y) return;
        par[x] = y; sz[y] += sz[x];
    }
};

namespace LCA {
    int timer = 0;
    vi tin(MAXN), tout(MAXN);
    vvi par(MAXN, vi(20));

    void dfs(int u, int p, int h){
        depth[u] = h;
        
        par[u][0] = p;
        for(int i = 1; i < 20; i++)
            par[u][i] = par[par[u][i-1]][i-1];

        tin[u] = timer++;
        for(auto v : adj[u])
            if(v != p) dfs(v, u, h+1);
        tout[u] = timer-1;
    }
    // Is u an ancestor of v?
    bool isAncestor(int u, int v){
        return tin[u] <= tin[v] and
            tout[v] <= tout[u];
    }

    int query(int u, int v){
        if(isAncestor(u, v)) return u;
        if(isAncestor(v, u)) return v;
        for(int i = 19; i >= 0; i--)
            if(!isAncestor(par[u][i], v))
                u = par[u][i];
        return par[u][0];
    }

    int query1(int u, int v){
        for(int i = 19; i >= 0; i--)
            if(!isAncestor(par[v][i], u))
                v = par[v][i];
        return v;
    }

    void init(){
        dfs(0, 0, 1);
    }
};

namespace BIT {
    vi arr(MAXN);
    void add(int x, int val){ x++;
        for(; x < MAXN; x += x&(-x))
            arr[x] += val;
    }
    int query(int x){ x++;
        int ans = 0;
        for(; x > 0; x -= x&(-x))
            ans += arr[x];
        return ans;
    }
};

struct PBDS {
    gp_hash_table<int, int> arr;

    void add(int x, int val){ x++;
        for(; x < MAXN; x += x&(-x))
            arr[x] += val;
    }
    int query(int x){ x++;
        int ans = 0;
        for(; x > 0; x -= x&(-x))
            ans += arr[x];
        return ans;
    } 
    void insert(int x){add(x, 1);};
    void erase(int x){add(x, -1);};
    
    int size(){return query(MAXN);}
    int order_of_key(int x){return query(x-1);}
};

namespace CD {
    unordered_set<int> pres;
    vi par(MAXN), cnt(MAXN);

    int dfs(int u, int p){
        cnt[u] = 1;
        for(auto v : adj[u])
            if(v != p and !pres.count(v))
                cnt[u] += dfs(v, u);
        return cnt[u];
    }
    int dfs(int u, int p, int sz){
        for(auto v : adj[u])
            if(v != p and !pres.count(v))
                if(cnt[v] > sz/2) return dfs(v, u, sz);
        return u;
    }

    void build(int u, int p){
        int sz = dfs(u,u), ct = dfs(u,u,sz);
        par[ct] = p; pres.insert(ct);
        for(auto v : adj[ct])
            if(!pres.count(v)) build(v, ct);
    }
    void init(){
        build(0, -1);
    }
};

bool inc(int u, int v){
    int p = LCA::query1(u, v);
    auto f = BIT::query(LCA::tin[v])-BIT::query(LCA::tin[p]);
    if(f == depth[v]-depth[p]) return true;
    return false;
}

bool dec(int u, int v){
    int p = LCA::query1(u, v);
    auto f = BIT::query(LCA::tin[v])-BIT::query(LCA::tin[p]);
    if(f == 0) return true;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K; cin >> N >> K;
    
    vector<array<int, 3>> Q(N+K-1);
    for(int x = 0; x < N+K-1; x++){
        char c; cin >> c;
        if(c == 'S'){
            int u, v; cin >> u >> v;
            u--, v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
            Q[x] = {0, u, v};
        }else if(c == 'Q'){
            int u, d; cin >> u >> d;
            u--, d--;
            Q[x] = {1, d, u};
        }else{
            int d; cin >> d;
            Q[x] = {2, --d, d};
        }
    }

    LCA::init(); DSU::init(); CD::init();

    vi isConnected(N);
    auto path_exists = [&](int u, int v)->bool{
        if(DSU::parent(u) != DSU::parent(v))
            return false;

        int p = LCA::query(u, v);

        if(p == u){
            if(inc(u, v)) return true;
        }else if(p == v){
            if(dec(v, u)) return true;
        }else{
            int p1 = LCA::query1(p, u), p2 = LCA::query1(p, v);

            if(dec(p, u) and inc(p, v) and isConnected[p1] < isConnected[p2])
                return true;
        }
        return false;        
    };

    PBDS jp[N]; set<ii> mc;
    auto uupp = [&](int u){
        for(int p = CD::par[u]; p != -1; p = CD::par[p]){
            if(!path_exists(p, u)) continue;
            if(mc.count({u, p})) continue;
            mc.insert({u, p});

            int p1;
            if(LCA::query(p, u) == p){
                p1 = LCA::query1(p, u);
            }else p1 = p;

            jp[p].insert(isConnected[p1]);
        }
    };

    for(uint x = 0; x < Q.size(); x++){
        if(Q[x][0] == 0){
            int u = Q[x][1], v = Q[x][2];
            if(depth[u] > depth[v]) swap(u, v);

            if(isConnected[u])
                BIT::add(LCA::tin[v], 1),
                BIT::add(LCA::tout[v]+1, -1);

            DSU::merge(u, v);
            isConnected[v] = x+1;

            uupp(u); uupp(v);

        }else if(Q[x][0] == 1){
            int u = Q[x][1], v = Q[x][2];
            if(path_exists(u, v)) cout << "yes\n";
            else cout << "no\n";
        
        }else{
            int u = Q[x][1], ans = 0;
            
            for(int p = u; p != -1; p = CD::par[p]){
                if(p != u and !path_exists(u, p)) continue;
                
                ans++;
                if(p == u){
                    ans += jp[u].size();
                }else if(LCA::query(u, p) == p){
                    int p1 = LCA::query1(p, u);
                    ans += jp[p].size()-jp[p].order_of_key(isConnected[p1]+1);
                } else{
                    ans += jp[p].size()-jp[p].order_of_key(isConnected[p]+1);
                }
            }

            // int ans1 = 0;
            // for(int v = 0; v < N; v++)
            //     if(v == u or path_exists(u, v)) ans1++;
            // assert(ans1 == ans);

            cout << ans << "\n";
        }
    }

    return 0;
}
/*
5 2
S 1 2
S 4 5
S 3 4
C 2
S 2 3
C 2
*/

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
servers.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5