제출 #566554

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

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const int MAX_N = 5e4 + 1;

bitset<MAX_N> component0[2 * MAX_N];
bitset<MAX_N> component1[2 * MAX_N];

struct Dsu {
    int n, ind;
    vi loga;
    vi par, t;
    vvi dp;
    Dsu() {}
    Dsu(int n, int ind): n(n), ind(ind) {
        par.resize(n), t.resize(n);
        dp.resize(1, vi(n));
        for (int i = 0; i < n; i++) {
            dp[0][i] = i;
            if (!ind) {
                component0[i][i] = true;
            } else component1[i][i] = true;
        }
        iota(all(par), 0);
    }
    inline void Add(int time) {
        par.push_back(n);
        t.push_back(time);
        dp[0].push_back(n);
        n++;
    }
    int Find(int i) {
        return par[i] == i ? i : par[i] = Find(par[i]);
    }
    void Union(int a, int b, int time) {
        int pa = Find(a), pb = Find(b);
        if (pa == pb) return;
        Add(time);
        par[pa] = par[pb] = n - 1;
        dp[0][pa] = dp[0][pb] = n - 1;
        if (!ind) {
            component0[n - 1] = component0[pa] | component0[pb];
        } else {
            component1[n - 1] = component1[pa] | component1[pb];
        }
    }
    void Build() {
        loga.resize(n + 1);
        for (int i = 2; i <= n; i++) loga[i] = loga[i >> 1] + 1;
        dp.resize(loga[n] + 1, vi(n));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j <= loga[n]; j++) {
                dp[j][i] = dp[j - 1][dp[j - 1][i]];
            }
        }
    }
    int Jump(int node, int time) {
        for (int i = loga[n]; i >= 0; i--) {
            if (t[dp[i][node]] <= time) {
                node = dp[i][node];
            }
        }
        return node;
    }
};

int ind[MAX_N];

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
    int m = x.size();
    Dsu d_min(n, 0), d_max(n, 1);
    iota(ind, ind + m, 0);
    sort(ind, ind + m, [&] (int i, int j) {
        return max(x[i], y[i]) < max(x[j], y[j]);
    });
    for (int i = 0; i < m; i++) {
        d_min.Union(x[ind[i]], y[ind[i]], max(x[ind[i]], y[ind[i]]));
    }
    d_min.Build();
    sort(ind, ind + m, [&] (int i, int j) {
        return min(x[i], y[i]) > min(x[j], y[j]);
    });
    for (int i = 0; i < m; i++) {
        d_max.Union(x[ind[i]], y[ind[i]], n - min(x[ind[i]], y[ind[i]]));
    }
    d_max.Build();
    int q = s.size();
    vi ans(q);
    for (int i = 0; i < q; i++) {
        int time_max = n - l[i], time_min = r[i];
        int v_max = d_max.Jump(s[i], time_max);
        int v_min = d_min.Jump(e[i], time_min);
        ans[i] = (component0[v_min] & component1[v_max]).any();
    }
    return ans;
}
//6 6 3
//0 3
//1 2
//1 5
//1 3
//2 5
//3 4
//
//4 2 1 2
//4 2 2 2
//5 4 3 4

//6 5 3
//1 3
//3 0
//0 4
//4 5
//5 2
//
//3 5 0 5
//2 1 0 4
//4 2 3 4

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