제출 #779446

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

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int N, timer;
vector<int> a[2], l[2], r[2], p[2];
vector<vector<int>> adj[2], ch[2];
void dfs(int z, int x) {
    l[z][x] = timer;
    for (int y : ch[z][x]) {
        dfs(z, y);
    }
    r[z][x] = ++timer;
    a[z].push_back(x);
}
void build(int z) {
    p[z].resize(N, N);
    l[z].resize(N);
    r[z].resize(N);
    ch[z].resize(N);
    vector<int> par(N);
    iota(par.begin(), par.end(), 0);
    function<int(int)> find = [&](int x) {
        return x == par[x] ? x : par[x] = find(par[x]);
    };
    for (int i = 0; i < N; i++) {
        for (int j : adj[z][i]) {
            if (j > i) {
                continue;
            }
            int x = find(j);
            if (x == i) {
                continue;
            }
            ch[z][i].push_back(x);
            p[z][x] = par[x] = i;
        }
    }
    timer = 0;
    dfs(z, N - 1);
}
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;
    adj[0].resize(N);
    adj[1].resize(N);
    for (int i = 0; i < X.size(); i++) {
        adj[0][X[i]].push_back(Y[i]);
        adj[0][Y[i]].push_back(X[i]);
        X[i] = N - 1 - X[i];
        Y[i] = N - 1 - Y[i];
        adj[1][X[i]].push_back(Y[i]);
        adj[1][Y[i]].push_back(X[i]);
    }
    build(0);
    build(1);
    for (int i = 0; i < N; i++) {
        a[1][i] = N - 1 - a[1][i];
        p[1][i] = N - 1 - p[1][i];
        for (int &x : ch[1][i]) {
            x = N - 1 - x;
        }
    }
    for (int i = 0; i < N / 2; i++) {
        swap(p[1][i], p[1][N - 1 - i]);
        swap(l[1][i], l[1][N - 1 - i]);
        swap(r[1][i], r[1][N - 1 - i]);
        swap(ch[1][i], ch[1][N - 1 - i]);
    }
    int Q = S.size();
    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        int t[2];
        t[0] = E[i];
        while (p[0][t[0]] <= R[i]) {
            t[0] = p[0][t[0]];
        }
        t[1] = S[i];
        while (p[1][t[1]] >= L[i]) {
            t[1] = p[1][t[1]];
        }
        vector<bool> f(N);
        for (int j = l[1][t[1]]; j < r[1][t[1]]; j++) {
            f[a[1][j]] = 1;
        }
        for (int j = l[0][t[0]]; j < r[0][t[0]]; j++) {
            if (f[a[0][j]]) {
                ans[i] = 1;
            }
        }
    }
    return ans;
}

컴파일 시 표준 에러 (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:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~

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