제출 #1140017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140017		woohyun_jng	Werewolf (IOI18_werewolf)	C++20	100 / 100	835 ms	135484 KiB

werewolf

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

#define MAX 300000
#define MAX_LOG 22

using namespace std;

vector<int> tree[MAX * 2], adj[MAX], child[MAX][2];
int N, union_par[MAX][2], A[MAX], in[MAX][2], out[MAX][2], cnt, parent[MAX][MAX_LOG][2];

int find(int t, int x) { return x == union_par[x][t] ? x : union_par[x][t] = find(t, union_par[x][t]); }

void dfs(int t, int n) {
    in[n][t] = cnt++;
    for (int i = 1; i < MAX_LOG; i++)
        if (parent[n][i - 1][t] != -1)
            parent[n][i][t] = parent[parent[n][i - 1][t]][i - 1][t];

    for (int i : child[n][t])
        dfs(t, i);
    out[n][t] = cnt;
}

void init() {
    for (int i = 0; i < N; i++)
        tree[i + N].push_back(A[i]);
    for (int i = N - 1; i > 0; i--) {
        tree[i].resize(tree[i << 1].size() + tree[i << 1 | 1].size());
        merge(tree[i << 1].begin(), tree[i << 1].end(), tree[i << 1 | 1].begin(), tree[i << 1 | 1].end(), tree[i].begin());
    }
}

int query(int l, int r, int x, int y) {
    int res = 0;
    for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            res += upper_bound(tree[l].begin(), tree[l].end(), y) - lower_bound(tree[l].begin(), tree[l].end(), x), l++;
        if (r & 1)
            r--, res += upper_bound(tree[r].begin(), tree[r].end(), y) - lower_bound(tree[r].begin(), tree[r].end(), x);
    }
    return res;
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y,
                           vector<int> S, vector<int> E,
                           vector<int> L, vector<int> R) {
    N = n;
    int M = X.size(), Q = S.size(), l, r, x, y, Z;

    for (int i = 0; i < M; i++)
        adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);

    for (int i = 0; i < N; i++) {
        union_par[i][0] = union_par[i][1] = i;
        for (int j = 0; j < MAX_LOG; j++)
            parent[i][j][0] = parent[i][j][1] = -1;
    }

    for (int i = N - 1; i >= 0; i--) {
        for (int j : adj[i]) {
            if (j < i || find(0, i) == find(0, j))
                continue;
            child[i][0].push_back(find(0, j));
            parent[find(0, j)][0][0] = i, union_par[find(0, j)][0] = i;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j : adj[i]) {
            if (j > i || find(1, i) == find(1, j))
                continue;
            child[i][1].push_back(find(1, j));
            parent[find(1, j)][0][1] = i, union_par[find(1, j)][1] = i;
        }
    }

    cnt = 0, dfs(0, 0);
    cnt = 0, dfs(1, N - 1);

    for (int i = 0; i < N; i++)
        A[in[i][0]] = in[i][1];
    init();

    vector<int> ans(Q);
    for (int i = 0; i < Q; ++i) {
        Z = S[i];
        for (int j = MAX_LOG - 1; j >= 0; j--)
            if (parent[Z][j][0] != -1 && parent[Z][j][0] >= L[i])
                Z = parent[Z][j][0];
        l = in[Z][0], r = out[Z][0] - 1;

        Z = E[i];
        for (int j = MAX_LOG - 1; j >= 0; j--) {
            if (parent[Z][j][1] != -1 && parent[Z][j][1] <= R[i])
                Z = parent[Z][j][1];
        }
        x = in[Z][1], y = out[Z][1] - 1;

        ans[i] = query(l, r, x, y) > 0;
    }

    return ans;
}

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