Submission #1296749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296749		orzshadownova	늑대인간 (IOI18_werewolf)	C++20	Compilation error	0 ms	0 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;
    }
};

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

    int N, M, Q;
    cin >> N >> M;

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

    cin >> Q;
    vector<int> S(Q), E(Q), L(Q), R(Q);
    for(int i=0;i<Q;i++) cin >> S[i];
    for(int i=0;i<Q;i++) cin >> E[i];
    for(int i=0;i<Q;i++) cin >> L[i];
    for(int i=0;i<Q;i++) cin >> R[i];

    // ---------- Build DSU for human -----------
    DSU dsuH(N);
    vector<int> compH(N+1);
    vector<bool> active(N+1, false);

    for(int v = N; v >= 1; v--){
        active[v] = true;
        for(int nxt : g[v]) if(active[nxt]){
            dsuH.unite(v, nxt);
        }
        compH[v] = dsuH.find(v);
    }

    // ---------- Build DSU for wolf  -------------
    DSU dsuW(N);
    fill(active.begin(), active.end(), false);

    vector<int> compW(N+1);
    for(int v = 1; v <= N; v++){
        active[v] = true;
        for(int nxt : g[v]) if(active[nxt]){
            dsuW.unite(v, nxt);
        }
        compW[v] = dsuW.find(v);
    }

    // ---------- Build pairs (compH[v], compW[v]) per node -------
    vector<pair<int,int>> A(N+1);
    for(int i=1;i<=N;i++){
        A[i] = { compH[i], compW[i] };
    }


    vector<pair<pair<int,int>,int>> all;
    for(int i=1;i<=N;i++){
        all.push_back({A[i], i});
    }

    sort(all.begin(), all.end());

    
    vector<int> id(N+1);
    int idCnt = 0;
    pair<int,int> last = {-1,-1};

    for(auto &p: all){
        if(p.first != last){
            last = p.first;
            idCnt++;
        }
        id[p.second] = idCnt;
    }


    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];

        int targetH = compH[s];
        int targetW = compW[e];

     

        
        int lo = 0, hi = N-1;
        pair<pair<int,int>,int> key = {{targetH, targetW}, -1};

        auto it = lower_bound(all.begin(), all.end(), key,
            [](auto &a, auto &b){
                return a.first < b.first;
            }
        );

        if(it != all.end() && it->first == key.first){
            int myId = id[it->second];

            
            auto &v = pos[myId];
            auto it2 = lower_bound(v.begin(), v.end(), l+1);

            if(it2 != v.end() && *it2 < r){
                ans[i] = 1;
            }
        }
    }

    
    for(int i=0;i<Q;i++){
        cout << ans[i] << "\n";
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccESHByC.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccjQ40sx.o:werewolf.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccESHByC.o: in function `main':
grader.cpp:(.text.startup+0x3ab): undefined reference to `check_validity(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status