Submission #964661

#	Time	Username	Problem	Language	Result	Execution time	Memory
964661		fve5	Werewolf (IOI18_werewolf)	C++17	49 / 100	400 ms	41528 KiB

werewolf

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

class SegTree {
    vector<int> arr;
    int sz, s;

    int upper_bound_right(int l, int r, int d, int n, int nb, int ne) {
        if (nb >= r || ne <= l || arr[n] <= d) return sz;
        if (nb + 1 == ne) return nb;

        int lq = upper_bound_right(l, r, d, 2 * n, nb, (nb + ne) / 2);
        if (lq != sz) return lq;

        return upper_bound_right(l, r, d, 2 * n + 1, (nb + ne) / 2, ne);
    }

    int upper_bound_left(int l, int r, int d, int n, int nb, int ne) {
        if (nb >= r || ne <= l || arr[n] <= d) return -1;
        if (nb + 1 == ne) return nb;

        int rq = upper_bound_left(l, r, d, 2 * n + 1, (nb + ne) / 2, ne);
        if (rq != -1) return rq;

        return upper_bound_left(l, r, d, 2 * n, nb, (nb + ne) / 2);
    }

public:
    int upper_bound_left(int l, int r, int d) { return upper_bound_left(l, r, d, 1, 0, s); }
    int upper_bound_right(int l, int r, int d) { return upper_bound_right(l, r, d, 1, 0, s); }

    SegTree(int N, const vector<int> &a) : sz(N) {
        s = 1 << (int)ceil(log2(N));
        arr.resize(2 * s);

        for (int i = 0; i < N; i++)
            arr[i + s] = a[i];
        for (int i = s - 1; i > 0; i--)
            arr[i] = max(arr[2 * i], arr[2 * i + 1]);
    }
};

vector<int> solve_naive(
    int N, int M, int Q,
    vector<int> X, vector<int> Y,
    vector<int> S, vector<int> E,
    vector<int> L, vector<int> R
) {
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        vector<array<bool, 2>> visited(N);
        queue<pair<int, bool>> q;

        q.emplace(S[i], 0);
        while (!q.empty()) {
            auto [node, st] = q.front(); q.pop();
            if (visited[node][st]) continue;
            visited[node][st] = true;
            
            for (auto x: adj[node]) {
                if (!st && x >= L[i]) q.emplace(x, st);
                if (st && x <= R[i]) q.emplace(x, st);
            }

            if (!st && L[i] <= node && node <= R[i]) q.emplace(node, 1);
        }

        ans[i] = visited[E[i]][1];
    }

    return ans;
}

vector<int> solve_line(
    int N, int M, int Q,
    vector<int> X, vector<int> Y,
    vector<int> S, vector<int> E,
    vector<int> L, vector<int> R
) {
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    int curr = find_if(adj.begin(), adj.end(), [](const vector<int> &arr) {
        return arr.size() == 1;
    }) - adj.begin();

    vector<int> line;
    line.push_back(curr);

    int old = -1;
    for (int i = 0; i < N - 1; i++) {
        curr = adj[curr][adj[curr][0] == old];
        old = line.back();
        line.push_back(curr);
    }

    vector<int> mline(N);
    transform(line.begin(), line.end(), mline.begin(), [](int x) { return  -x; });

    vector<int> pos_of(N);
    for (int i = 0; i < N; i++)
        pos_of[line[i]] = i;

    SegTree segtree(N, line), msegtree(N, mline);
    vector<int> ans(Q);

    for (int i = 0; i < Q; i++) {
        int l1 = msegtree.upper_bound_left(0, pos_of[S[i]] + 1, -L[i]);
        int r1 = msegtree.upper_bound_right(pos_of[S[i]], N, -L[i]);

        int l2 = segtree.upper_bound_left(0, pos_of[E[i]] + 1, R[i]);
        int r2 = segtree.upper_bound_right(pos_of[E[i]], N, R[i]);

        ans[i] = !((l2 >= r1 - 1) || (r2 <= l1 + 1));
    }

    return ans;
}

vector<int> check_validity(
    int N,
    vector<int> X, vector<int> Y,
    vector<int> S, vector<int> E,
    vector<int> L, vector<int> R
) {
    int M = X.size();
    int Q = S.size();

    if (N <= 3000 && M <= 6000 && Q <= 3000) {
        return solve_naive(N, M, Q, X, Y, S, E, L, R);
    }
    return solve_line(N, M, Q, X, Y, S, E, L, R);
}

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