Submission #1225624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225624		nicolo_010	Werewolf (IOI18_werewolf)	C++20	34 / 100	1561 ms	500872 KiB

werewolf

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll  = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
template<typename T>
using v = vector<T>;
const int INF = 1e9;

v<int> h;
v<v<int>> adj;

void dfs(int n, int p=0, int d=0) {
    h[n] = d;
    for (auto x : adj[n]) {
        if (h[x] == -1) {
            dfs(x, n, d+1);
        }
    }
}

int kthmx(int m, v<v<v<int>>> &lift, int rb) {
    for (int i = 20; i >= 0; i--) {
        if (lift[m][i][1] <= rb) {
            m = lift[m][i][0];
        }
    }
    return m;
}

int kthmn(int m, v<v<v<int>>> &lift, int lb) {
    for (int i = 20; i >= 0; i--) {
        if (lift[m][i][2] >= lb) {
            m = lift[m][i][0];
        }
    }
    return m;
}

//inicio esta a la izquierda del termino

bool check1(int a, int b) {
    if (a == 0 || b == 0) return true;
    else return (h[a] >= h[b]);
}

//inicio esta a la derecha del termino

bool check2(int a, int b) {
    if (a == 0 || b == 0) return true;
    else return (h[a] <= h[b]);
}

v<int> check_validity(int N, v<int> X, v<int> Y, v<int> S, v<int> E, v<int> L, v<int> R) {
    int n = N;
    adj.resize(n+1);
    int m = X.size();
    rep(i, 0, m) {
        X[i]++, Y[i]++;
    }
    rep(i, 0, m){
        int a = X[i], b = Y[i];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    h.assign(n+1, -1);
    v<v<v<int>>> leftt(n+1, v<v<int>>(21, v<int>(3)));
    v<v<v<int>>> rightt(n+1, v<v<int>>(21, v<int>(3)));
    rep(i, 0, n+1) {
        rep(j, 0, 21) {
            leftt[i][j] = {0, 0, INF};
            rightt[i][j] = {0, 0, INF};
        }
    }
    v<int> a(n+1);
    int u = 1;
    rep(i, 1, n+1) {
        if (adj[i].size() == 1) {
            u = i;
            break;
        }
    }
    dfs(u);
    rep(i, 1, n+1) {
        a[h[i]] = i;
    }
    //lift[i][j][0] = 2^j ancestro, lift[i][j][1] = max, lift[i][j][2] = min
    rep(i, 0, n) {
        if (i == 0) leftt[a[i]][0] = {0, INF, 0};
        else leftt[a[i]][0] = {a[i-1], a[i-1], a[i-1]};
        if (i == n-1) rightt[a[i]][0] = {0, INF, 0};
        else rightt[a[i]][0] = {a[i+1], a[i+1], a[i+1]};
    }
    rep(j, 1, 21) {
        rep(i, 1, n+1) {
            //left
            leftt[i][j][0] = leftt[leftt[i][j-1][0]][j-1][0];
            leftt[i][j][1] = max(leftt[i][j-1][1], leftt[leftt[i][j-1][0]][j-1][1]);
            leftt[i][j][2] = min(leftt[i][j-1][2], leftt[leftt[i][j-1][0]][j-1][2]);
            //right
            rightt[i][j][0] = rightt[rightt[i][j-1][0]][j-1][0];
            rightt[i][j][1] = max(rightt[i][j-1][1], rightt[rightt[i][j-1][0]][j-1][1]);
            rightt[i][j][2] = min(rightt[i][j-1][2], rightt[rightt[i][j-1][0]][j-1][2]);
        }
    }
    int q = L.size();
    v<int> ans(q);
    rep(i, 0, q) {
        S[i]++; E[i]++;
        L[i]++; R[i]++;
    }
    rep(i, 0, q) {
        int s = S[i], e = E[i];
        //cout << s << " " << e << endl;
        if (h[s] < h[e]) {
            int smn = kthmn(s, rightt, L[i]);
            int emx = kthmx(e, leftt, R[i]);
            if (check1(smn, emx)) ans[i] = 1;
            else ans[i] = 0;
        }
        else {
            int smn = kthmn(s, leftt, L[i]);
            int emx = kthmx(e, rightt, R[i]);
            //cout << smn << " " << emx << endl;
            if (check2(smn, emx)) ans[i] = 1;
            else ans[i] = 0;
        }
    }
    //for (auto x : ans) cerr << x << " ";
    //cout << endl;
    return ans;
}

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