oj.uz

Submission #1045511

# Submission time Handle Problem Language Result Execution time Memory
1045511 2024-08-06T04:41:01 Z yanb Werewolf (IOI18_werewolf) C++14
34 / 100
 1847 ms 42576 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1689 ms 34168 KB Output is correct
2 Correct 1788 ms 42568 KB Output is correct
3 Correct 1842 ms 42576 KB Output is correct
4 Correct 1795 ms 42572 KB Output is correct
5 Correct 1751 ms 42568 KB Output is correct
6 Correct 1734 ms 42572 KB Output is correct
7 Correct 1769 ms 42428 KB Output is correct
8 Correct 1711 ms 42344 KB Output is correct
9 Correct 883 ms 42576 KB Output is correct
10 Correct 1306 ms 42420 KB Output is correct
11 Correct 1441 ms 42552 KB Output is correct
12 Correct 1034 ms 42336 KB Output is correct
13 Correct 1811 ms 42424 KB Output is correct
14 Correct 1847 ms 42572 KB Output is correct
15 Correct 1770 ms 42420 KB Output is correct
16 Correct 1759 ms 42568 KB Output is correct
17 Correct 1766 ms 42564 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -