제출 #1296754

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1296754		orzshadownova	늑대인간 (IOI18_werewolf)	C++20	0 / 100	167 ms	45964 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p;
    DSU(int n=0){ init(n); }
    void init(int n){
        p.resize(n+1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    void unite(int a, int b){
        a = find(a); b = find(b);
        if(a != b) p[b] = a;
    }
};

static inline long long pack_pair(int a, int b){
    // pack two ints into a 64-bit key
    return ( (long long)a << 32 ) ^ (unsigned long long)b;
}

vector<int> check_validity(
    int N,
    vector<int> X,
    vector<int> Y,
    vector<int> S,
    vector<int> E,
    vector<int> L,
    vector<int> R
){
    int M = (int)X.size();
    int Q = (int)S.size();

    vector<vector<int>> g(N+1);
    for(int i=0;i<M;i++){
        int x = X[i], y = Y[i];
        g[x].push_back(y);
        g[y].push_back(x);
    }

    
    DSU dsuH(N);
    vector<int> compH(N+1);
    vector<char> active(N+1, 0);
    for(int v = N; v >= 1; --v){
        active[v] = 1;
        for(int nx : g[v]) if(active[nx]) dsuH.unite(v, nx);
        compH[v] = dsuH.find(v);
    }

    
    DSU dsuW(N);
    fill(active.begin(), active.end(), 0);
    vector<int> compW(N+1);
    for(int v = 1; v <= N; ++v){
        active[v] = 1;
        for(int nx : g[v]) if(active[nx]) dsuW.unite(v, nx);
        compW[v] = dsuW.find(v);
    }

    
    unordered_map<long long,int> mp;
    mp.reserve(N*2);
    vector<int> id(N+1, 0);
    int idCnt = 0;

    for(int v=1; v<=N; ++v){
        long long key = pack_pair(compH[v], compW[v]);
        auto it = mp.find(key);
        if(it == mp.end()){
            ++idCnt;
            mp.emplace(key, idCnt);
            id[v] = idCnt;
        } else {
            id[v] = it->second;
        }
    }

    vector<vector<int>> pos(idCnt+1);
    for(int v=1; v<=N; ++v) pos[id[v]].push_back(v);
    for(int i=1;i<=idCnt;i++) sort(pos[i].begin(), pos[i].end());

    
    vector<int> ans(Q, 0);
    for(int i=0;i<Q;i++){
        int s = S[i], e = E[i], l = L[i], r = R[i];
        if(!(l+1 < r)){ // no valid T exists
            ans[i] = 0;
            continue;
        }
        long long key = pack_pair(compH[s], compW[e]);
        auto it = mp.find(key);
        if(it == mp.end()){
            ans[i] = 0;
            continue;
        }
        int myId = it->second;
        auto &vec = pos[myId];
        // find smallest position >= l+1
        auto it2 = lower_bound(vec.begin(), vec.end(), l+1);
        if(it2 != vec.end() && *it2 < r) ans[i] = 1;
        else ans[i] = 0;
    }

    return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51