Submission #138235

#	Time	Username	Problem	Language	Result	Execution time	Memory
138235		fredbr	Werewolf (IOI18_werewolf)	C++17	0 / 100	4046 ms	29532 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct Seg {
    struct Node {
        int mini, maxi;

        static Node join(Node const& a, Node const& b) {
            return Node{min(a.mini, b.mini), max(a.maxi, b.maxi)};
        }
    };

    int n;
    vector<Node> tree;
    vector<int> const& v;

    Seg(vi const& v) : n(v.size()), tree(n*4), v(v) {
        build(0, 0, n-1);
    };

    void build(int no, int l, int r) {
        if (l == r) {
            tree[no] = Node{v[l], v[l]};
            return;
        }

        int m = (l+r)/2;
        
        build(no*2+1, l, m);
        build(no*2+2, m+1, r);

        tree[no] = Node::join(tree[no*2+1], tree[no*2+2]);
    }

    Node get(int no, int l, int r, int a, int b) {
        if (a <= l and r <= b) return tree[no];

        int m = (l+r)/2;

        if (b <= m) return get(no*2+1, l, m, a, b);
        if (a > m) return get(no*2+2, m+1, r, a, b);

        return Node::join(get(no*2+1, l, m, a, b),
                          get(no*2+2, m+1, r, a, b));
    }
};

int const maxn = 202020;

vector<int> vt[maxn];

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 q = S.size();

    for (int i = 0; i < n; i++) {
        vt[X[i]].push_back(Y[i]);
        vt[Y[i]].push_back(X[i]);
    }

    int beg = 0;
    for (int i = 0; i < n; i++) if (vt[i].size() == 1) beg = i;

    vector<int> v(n);
    v[0] = beg;
    vector<int> pos(n, -1);
    pos[beg] = 0;

    for (int i = 1; i < n; i++) {
        int last = v[i-1];

        for (int u : vt[last]) {
            if (pos[u] != -1) continue;

            v[i] = u;
            pos[u] = i;
        }
    }
    
    vector<int> res(q);
    Seg sg(v);

    for (int i = 0; i < q; i++) {
        int source = S[i], dest = E[i];
        
        if (pos[source] > pos[dest]) swap(source, dest);

        int l = L[i], r = R[i];

        int x = pos[source], y = pos[dest] + 1;

        while (y-x > 1) { // last human end
            int m = (x+y)/2;

            if (sg.get(0, 0, n-1, pos[source], m).mini < l) y = m;
            else x = m;
        }

        if (sg.get(0, 0, n-1, pos[source], x).mini < l) {
            res[i] = 0;
            continue;
        }

        int ml = x;

        x = pos[source]-1, y = pos[dest];

        while (y-x > 1) { // werewolf begin
            int m = (x+y+1)/2;

            if (sg.get(0, 0, n-1, m, pos[dest]).maxi > r) x = m;
            else y = m;
        }

        if (sg.get(0, 0, n-1, y, pos[dest]).maxi > r) {
            res[i] = 0;
            continue;
        }

        res[i] = ml >= y;
    }

    return res;
}

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