Submission #779456

#	Time	Username	Problem	Language	Result	Execution time	Memory
779456		t6twotwo	Werewolf (IOI18_werewolf)	C++17	15 / 100	4075 ms	86028 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) {
                int x = find(j);
                if (x != i) {
                    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 par[2][N][18];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 18; j++) {
            par[0][i][j] = N;
            par[1][i][j] = -1;
        }
    }
    for (int i = N - 1; i >= 0; i--) {
        par[0][i][0] = p[0][i];
        for (int j = 0; j < 17 && par[0][i][j] != N; j++) {
            par[0][i][j + 1] = par[0][par[0][i][j]][j];
        }
    }
    for (int i = 0; i < N; i++) {
        par[1][i][0] = p[1][i];
        for (int j = 0; j < 17 && par[1][i][j] != -1; j++) {
            par[1][i][j + 1] = par[1][par[1][i][j]][j];
        }
    }
    int Q = S.size();
    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        int t[2];
        t[0] = E[i];
        for (int j = 17; j >= 0; j--) {
            if (par[0][t[0]][j] <= R[i]) {
                t[0] = par[0][t[0]][j];
            }
        }
        t[1] = S[i];
        for (int j = 17; j >= 0; j--) {
            if (par[1][t[1]][j] >= L[i]) {
                t[1] = par[1][t[1]][j];
            }
        }
        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;
}

Compilation message (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:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~

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