제출 #163703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163703		dolphingarlic	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1493 ms	141180 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

vector<int> dsu_tree[2][200000], graph[200000];
int N, p[2][20][200000], timer, cmp[2][200000], order[2][200000];
pair<int, int> bounds[2][200000];

void dfs(int node, int t) {
    bounds[t][node] = {timer, timer};
    order[t][timer] = node;
    timer++;

    FOR(i, 1, 20) {
        if (p[t][i - 1][node] == -1) break;
        p[t][i][node] = p[t][i - 1][p[t][i - 1][node]];
    }

    for (int i : dsu_tree[t][node]) {
        p[t][0][i] = node;
        dfs(i, t);
        bounds[t][node].second =
            max(bounds[t][node].second, bounds[t][i].second);
    }
}

int find(int a, int t) {
    while (a != cmp[t][a]) cmp[t][a] = cmp[t][cmp[t][a]], a = cmp[t][a];
    return a;
}
void onion(int a, int b, int t) {
    cmp[t][find(a, t)] = cmp[t][find(b, t)];
}

vector<int> segtree[800000];
void build(int node = 1, int l = 0, int r = N - 1) {
    if (l == r) segtree[node] = {bounds[0][order[1][l]].first};
    else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        
        int lptr = 0, rptr = 0;
        int lsz = segtree[node * 2].size(), rsz = segtree[node * 2 + 1].size();
        while (lptr < lsz && rptr < rsz) {
            if (segtree[node * 2][lptr] < segtree[node * 2 + 1][rptr]) {
                segtree[node].push_back(segtree[node * 2][lptr++]);
            } else {
                segtree[node].push_back(segtree[node * 2 + 1][rptr++]);
            }
        }
        while (lptr < lsz) segtree[node].push_back(segtree[node * 2][lptr++]);
        while (rptr < rsz) segtree[node].push_back(segtree[node * 2 + 1][rptr++]);
    }
}

bool query(int a, int b, int x, int y, int node = 1, int l = 0, int r = N - 1) {
    if (r < a || l > b) return false;
    if (r <= b && l >= a)
        return (
            upper_bound(segtree[node].begin(), segtree[node].end(), y) -
                lower_bound(segtree[node].begin(), segtree[node].end(), x) !=
            0);
    int mid = (l + r) / 2;
    return (query(a, b, x, y, node * 2, l, mid) ||
            query(a, b, x, y, node * 2 + 1, mid + 1, r));
}

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 Q = S.size();
    vector<int> A(Q);

    FOR(i, 0, N) cmp[0][i] = cmp[1][i] = i;
    FOR(i, 0, X.size()) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    for (int i = N - 1; ~i; i--)
        for (int j : graph[i])
            if (j > i && find(j, 0) != find(i, 0)) {
                dsu_tree[0][i].push_back(find(j, 0));
                onion(j, i, 0);
            }
    for (int i = 0; i < N; i++)
        for (int j : graph[i])
            if (j < i && find(j, 1) != find(i, 1)) {
                dsu_tree[1][i].push_back(find(j, 1));
                onion(j, i, 1);
            }

    memset(p, -1, sizeof(p));

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

    build();

    FOR(i, 0, Q) {
        int X = S[i], Y = E[i];
        for (int j = 19; ~j; j--) {
            if (~p[0][j][X] && p[0][j][X] >= L[i]) X = p[0][j][X];
            if (~p[1][j][Y] && p[1][j][Y] <= R[i]) Y = p[1][j][Y];
        }
        A[i] = query(bounds[1][Y].first, bounds[1][Y].second, bounds[0][X].first, bounds[0][X].second);
    }

    return A;
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:3:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
werewolf.cpp:78:9:
     FOR(i, 0, X.size()) {
         ~~~~~~~~~~~~~~                  
werewolf.cpp:78:5: note: in expansion of macro 'FOR'
     FOR(i, 0, X.size()) {
     ^~~

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