Submission #1296752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296752		orzshadownova	Werewolf (IOI18_werewolf)	C++20	0 / 100	184 ms	40308 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;
    }
};

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 = X.size();
    int Q = 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 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);
    }

    // ---------- 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 ----------
    vector<pair<int,int>> A(N+1);
    for(int v=1; v<=N; v++){
        A[v] = {compH[v], compW[v]};
    }

    vector<pair<pair<int,int>,int>> all;
    for(int v=1; v<=N; v++){
        all.push_back({A[v], v});
    }
    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());

    // ---------- Answer queries ----------
    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];

        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 &vec = pos[myId];

            auto it2 = lower_bound(vec.begin(), vec.end(), l+1);
            if(it2 != vec.end() && *it2 < r){
                ans[i] = 1;
            }
        }
    }

    return ans;
}

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