Submission #1296755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296755		orzshadownova	Werewolf (IOI18_werewolf)	C++20	0 / 100	170 ms	46040 KiB

werewolf

#include "werewolf.h"
#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){
    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 = X.size();
    int Q = S.size();

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

    // -------- DSU for human form (cities >= threshold) --------
    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 for wolf form (cities <= threshold) --------
    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);
    }

    // -------- compress pairs (compH, compW) --------
    unordered_map<long long, int> mp;
    mp.reserve(N * 2);

    vector<int> id(N+1);
    int idCnt = 0;

    for(int v = 1; v <= N; v++){
        long long key = pack_pair(compH[v], compW[v]);
        if(!mp.count(key)){
            mp[key] = ++idCnt;
        }
        id[v] = mp[key];
    }

    // store positions for each id
    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];

        // T must satisfy (l < T < r)
        if(!(l + 1 < r)){
            ans[i] = 0;
            continue;
        }

        long long key = pack_pair(compH[s], compW[e]);

        if(!mp.count(key)){
            ans[i] = 0;
            continue;
        }

        int myId = mp[key];
        auto &vec = pos[myId];

        // find smallest T >= l+1
        auto it = lower_bound(vec.begin(), vec.end(), l + 1);

        if(it != vec.end() && *it < 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