Submission #1221556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221556		not_amir	Werewolf (IOI18_werewolf)	C++20	100 / 100	961 ms	202656 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
    vector<vector<int>> G(N);
    assert(X.size() == Y.size());
    int M = X.size();
    for (int i = 0; i < M; i++) {
        G[X[i]].push_back(Y[i]);
        G[Y[i]].push_back(X[i]);
    }
    vector<int> p(N), we(N, -1), siz(N, 1);
    iota(p.begin(), p.end(), 0);
    for (int i = N - 1; i >= 0; i--) {
        for (int u : G[i]) {
            if (u < i)
                continue;
            int v = i;
            while (u != p[u])
                u = p[u];
            while (v != p[v])
                v = p[v];
            if (u == v)
                continue;
            if (siz[u] > siz[v])
                swap(u, v);
            p[u] = v;
            we[u] = i;
            siz[v] += siz[u];
        }
    }
    vector<map<int, int>> s(N);
    for (int i = 0; i < N; i++) {
        int v = i;
        s[i][v] = i;
        while (v != p[v]) {
            s[i][p[v]] = we[v];
            v = p[v];
        }
    }
    vector<vector<tuple<int, int, int, int>>> qu(N);
    int Q = L.size();
    assert(R.size() == Q && S.size() == Q && E.size() == Q);
    for (int i = 0; i < Q; i++)
        qu[R[i]].push_back({E[i], S[i], L[i], i});
    vector<int> np(N), A(Q);
    iota(np.begin(), np.end(), 0);
    for (int i = 0; i < N; i++) {
        for (int u : G[i]) {
            if (u > i)
                continue;
            int v = i;
            while (u != np[u])
                u = np[u];
            while (v != np[v])
                v = np[v];
            if (u == v)
                continue;
            if (s[u].size() > s[v].size())
                swap(u, v);
            np[u] = v;
            for (auto [x, c] : s[u])
                s[v][x] = max(s[v][x], c);
        }
        for (auto [u, v, l, idx] : qu[i]) {
            while (u != np[u])
                u = np[u];
            while (we[v] >= l)
                v = p[v];
            A[idx] = s[u][v] >= l;
        }
    }
    return A;
}

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