Submission #138287

#	Time	Username	Problem	Language	Result	Execution time	Memory
138287		fredbr	Werewolf (IOI18_werewolf)	C++17	34 / 100	4008 ms	45356 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;
        }
    }
    auto v2 = v;
    reverse(v2.begin(), v2.end());

    auto posinv = pos;
    for (int& i : posinv) i = n-i-1;

    vector<int> res(q);
    Seg sg(v), sginv(v2);

    for (int i = 0; i < q; i++) {
        int source = S[i], dest = E[i];
        int l = L[i], r = R[i];
        
        if (pos[source] > pos[dest]) {
            int x = posinv[source] - 1, y = posinv[dest];

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

                if (sginv.get(0, 0, n-1, m, posinv[dest]).maxi <= r) y = m;
                else x = m;
            }
            res[i] = (sginv.get(0, 0, n-1, posinv[source], y).mini >= l and
                      sginv.get(0, 0, n-1, y, posinv[dest]).maxi <= r);
        }
        else {
            int x = pos[source] - 1, y = pos[dest];

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

                if (sg.get(0, 0, n-1, m, pos[dest]).maxi <= r) y = m;
                else x = m;
            }
            res[i] = (sg.get(0, 0, n-1, pos[source], y).mini >= l and
                      sg.get(0, 0, n-1, y, pos[dest]).maxi <= r);
        }
    }

    return res;
}

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