제출 #1077395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1077395		vjudge1	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4033 ms	20808 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct DSU {
    vi e;
    DSU(int n) : e(n, -1) {}
    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    void join(int u, int v) {
        u = repr(u);
        v = repr(v);
        if(u == v) return;
        if(e[u] >= e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
    }

    bool same(int u, int v) {
        return repr(u) == repr(v);
    }
};

vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int q = (int)S.size(), m = (int)X.size();
    vi Re(q, 0);
    for(int nr = 0; nr < q; ++nr) {
        DSU St(n), Dr(n);
        for(int i = 0; i < m; ++i) {
            if(X[i] <= R[nr] && Y[i] <= R[nr])
                St.join(X[i], Y[i]);
            if(X[i] >= L[nr] && Y[i] >= L[nr])
                Dr.join(X[i], Y[i]);
        }
        for(int i = L[nr]; i <= R[nr]; ++i) {
            if(Dr.same(i, S[nr]) && St.same(i, E[nr])) Re[nr] = 1;
        }
    }
    return Re;
}

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