Submission #1045511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045511		yanb	Werewolf (IOI18_werewolf)	C++14	34 / 100	1847 ms	42576 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

struct MaxSegTree {
    int n;
    vector<int> st;

    void build(int v, int vl, int vr, vector<int> &a) {
        if (vl == vr) {
            st[v] = a[vl];
            return;
        }
        int vm = (vl + vr) / 2;
        build(v * 2, vl, vm, a);
        build(v * 2 + 1, vm + 1, vr, a);
        st[v] = max(st[v * 2], st[v * 2 + 1]);
    }

    MaxSegTree(int n, vector<int> a) {
        this->n = n;
        st.resize(4 * n);
        build(1, 0, n - 1, a);
    }

    int get(int l, int r, int v, int vl, int vr) {
        if (vr < l || r < vl) return -1e9;
        if (l <= vl && vr <= r) return st[v];
        int vm = (vl + vr) / 2;
        return max(get(l, r, v * 2, vl, vm), get(l, r, v * 2 + 1, vm + 1, vr));
    }
};

void dfs(int v, int mn, int mx, vector<vector<int>> &g, vector<bool> &uu) {
    if (uu[v] || v > mx || v < mn) return;
    uu[v] = 1;
    for (int u : g[v]) {
        dfs(u, mn, mx, g, uu);
    }
}

vector<int> def(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);
    for (int i = 0; i < X.size(); i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    int q = S.size();
    vector<int> ans(q);
    for (int t = 0; t < q; t++) {
        vector<bool> uuw(N), uuh(N);
        dfs(E[t], 0, R[t], g, uuw);
        dfs(S[t], L[t], N, g, uuh);
        for (int i = 0; i < N; i++) {
            if (uuw[i] && uuh[i]) ans[t] = 1;
        }
    }

    return ans;
}

vector<int> segt(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int q = S.size();
    vector<vector<int>> g(N);
    for (int i = 0; i < X.size(); i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    vector<int> a, aT(N);
    vector<bool> uu(N);
    for (int i = 0; i < N; i++) {
        if (g[i].size() == 1) {
            a.push_back(i);
            aT[i] = 0;
            uu[i] = 1;
            break;
        }
    }

    for (int i = 1; i < N; i++) {
        for (int u : g[a.back()]) {
            if (!uu[u]) {
                aT[u] = a.size();
                a.push_back(u);
                uu[u] = 1;
                break;
            }
        }
    }

    //for (int x : a) cout << x << " ";
    //cout << "\n";

    MaxSegTree mxst(N, a);
    for (int i = 0; i < N; i++) a[i] *= -1;
    MaxSegTree mnst(N, a);

    vector<int> ans(q);

    for (int t = 0; t < q; t++) {
        int l, r;

        l = -1, r = aT[S[t]];
        while (r - l > 1) {
            int md = (l + r) / 2;
            if (mnst.get(md, aT[S[t]], 1, 0, N - 1) <= -L[t]) r = md;
            else l = md;
        }
        int ls = r;

        l = aT[S[t]], r = N;
        while (r - l > 1) {
            int md = (l + r) / 2;
            if (mnst.get(aT[S[t]], md, 1, 0, N - 1) <= -L[t]) l = md;
            else r = md;
        }
        int rs = l;

        l = -1, r = aT[E[t]];
        while (r - l > 1) {
            int md = (l + r) / 2;
            if (mxst.get(md, aT[E[t]], 1, 0, N - 1) <= R[t]) r = md;
            else l = md;
        }
        int le = r;

        l = aT[E[t]], r = N;
        while (r - l > 1) {
            int md = (l + r) / 2;
            if (mxst.get(aT[E[t]], md, 1, 0, N - 1) <= R[t]) l = md;
            else r = md;
        }
        int re = l;

        //cout << t << "\tHUMAN: " << ls << "~" << rs << "\tWOLF: " << le << "~" << re << "\n";

        ans[t] = (re >= ls && rs >= le);
    }

    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) {
    return segt(N, X, Y, S, E, L, R);
    return def(N, X, Y, S, E, L, R);
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> def(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> segt(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~

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