Submission #425483

#	Time	Username	Problem	Language	Result	Execution time	Memory
425483		KoD	Werewolf (IOI18_werewolf)	C++17	49 / 100	809 ms	57736 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

template <class T> using Vec = std::vector<T>;

struct RMQ {
    Vec<Vec<int>> mintable;
    Vec<Vec<int>> maxtable;
    RMQ(const Vec<int>& vec) {
        const int n = (int) vec.size();
        int k = 0;
        while ((1 << k) <= n) {
            k += 1;
        }
        mintable.resize(k);
        maxtable.resize(k);
        mintable[0] = vec;
        maxtable[0] = vec;
        for (int h = 0; h < k - 1; ++h) {
            const int len = n - (1 << (h + 1)) + 1;
            mintable[h + 1].resize(len);
            maxtable[h + 1].resize(len);
            for (int i = 0; i < len; ++i) {
                mintable[h + 1][i] = std::min(mintable[h][i], mintable[h][i + (1 << h)]);
                maxtable[h + 1][i] = std::max(maxtable[h][i], maxtable[h][i + (1 << h)]);
            }
        }
    }
    int min(const int l, const int r) const {
        if (l == r) {
            return std::numeric_limits<int>::max();
        }
        const int h = 31 - __builtin_clz(r - l);
        return std::min(mintable[h][l], mintable[h][r - (1 << h)]);
    }
    int max(const int l, const int r) const {
        if (l == r) {
            return std::numeric_limits<int>::min();
        }
        const int h = 31 - __builtin_clz(r - l);
        return std::max(maxtable[h][l], maxtable[h][r - (1 << h)]);
    }
};

template <class Func> int binary_search(int ok, int ng, const Func& f) {
    while (std::abs(ok - ng) > 1) {
        const int md = (ok + ng) / 2;
        (f(md) ? ok : ng) = md;
    }
    return ok;
}

Vec<int> check_validity(int N, Vec<int> X, Vec<int> Y, Vec<int> S, Vec<int> E, Vec<int> L, Vec<int> R) {
    const int M = (int) X.size();
    const int Q = (int) S.size();
    Vec<Vec<int>> graph(N);
    for (int i = 0; i < M; ++i) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }
    if (N <= 3000 and M <= 6000 and Q <= 3000) {
        Vec<int> ret(Q);
        for (int i = 0; i < Q; ++i) {
            Vec<char> state(N);
            Vec<int> que;
            que.reserve(N);
            {
                const auto push = [&](const int u) {
                    if (u >= L[i] and !(state[u] & 1)) {
                        state[u] |= 1;
                        que.push_back(u);
                    }
                };
                push(S[i]);
                while (!que.empty()) {
                    const auto u = que.back();
                    que.pop_back();
                    for (const auto v : graph[u]) {
                        push(v);
                    }
                }
            }
            {
                const auto push = [&](const int u) {
                    if (u <= R[i] and !(state[u] & 2)) {
                        state[u] |= 2;
                        que.push_back(u);
                    }
                };
                push(E[i]);
                while (!que.empty()) {
                    const auto u = que.back();
                    que.pop_back();
                    for (const auto v : graph[u]) {
                        push(v);
                    }
                }
            }
            ret[i] = std::any_of(state.begin(), state.end(), [&](const int x) { return x == 3; });
        }
        return ret;
    } else {
        Vec<int> line;
        line.reserve(N);
        {
            int u = 0;
            while ((int) graph[u].size() != 1) {
                u += 1;
            }
            Vec<char> done(N);
            while (!done[u]) {
                line.push_back(u);
                done[u] = true;
                for (const auto v : graph[u]) {
                    if (!done[v]) {
                        u = v;
                        break;
                    }
                }
            }
        }
        Vec<int> idx(N);
        for (int i = 0; i < N; ++i) {
            idx[line[i]] = i;
        }
        RMQ rmq(line);
        Vec<int> ret(Q);
        for (int i = 0; i < Q; ++i) {
            const int u = S[i];
            const int v = E[i];
            if (idx[u] < idx[v]) {
                const auto right = binary_search(idx[u], N, [&](const int r) {
                    return rmq.min(idx[u], r + 1) >= L[i];
                });
                const auto left = binary_search(idx[v], -1, [&](const int l) {
                    return rmq.max(l, idx[v] + 1) <= R[i];
                });      
                ret[i] = right >= left;          
            } else {
                const auto left = binary_search(idx[u], -1, [&](const int l) {
                    return rmq.min(l, idx[u] + 1) >= L[i];
                });
                const auto right = binary_search(idx[v], N, [&](const int r) {
                    return rmq.max(idx[v], r + 1) <= R[i];
                });      
                ret[i] = right >= left;                    
            }
        }
        return ret;
    }
}

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