oj.uz

Submission #1045514

# Submission time Handle Problem Language Result Execution time Memory
1045514 2024-08-06T04:43:49 Z yanb Werewolf (IOI18_werewolf) C++14
49 / 100
 4000 ms 45964 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) {
    int m = X.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]);
    }
    bool line = 0;
    if (m + 1 == N) line = 1;
    for (int i = 0; i < N; i++) {
        if (g[i].size() > 2) line = 0; 
    }

    if (line) 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++) {
      |                     ~~^~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:148:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 170 ms 856 KB Output is correct
11 Correct 61 ms 856 KB Output is correct
12 Correct 12 ms 1112 KB Output is correct
13 Correct 173 ms 860 KB Output is correct
14 Correct 73 ms 980 KB Output is correct
15 Correct 161 ms 1116 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1727 ms 45132 KB Output is correct
2 Correct 1789 ms 44992 KB Output is correct
3 Correct 1840 ms 44988 KB Output is correct
4 Correct 1884 ms 44916 KB Output is correct
5 Correct 1839 ms 45132 KB Output is correct
6 Correct 1748 ms 45248 KB Output is correct
7 Correct 1790 ms 45128 KB Output is correct
8 Correct 1790 ms 45244 KB Output is correct
9 Correct 927 ms 45192 KB Output is correct
10 Correct 1391 ms 45128 KB Output is correct
11 Correct 1536 ms 44932 KB Output is correct
12 Correct 1143 ms 45124 KB Output is correct
13 Correct 1983 ms 45124 KB Output is correct
14 Correct 1823 ms 44992 KB Output is correct
15 Correct 1936 ms 45128 KB Output is correct
16 Correct 1935 ms 45132 KB Output is correct
17 Correct 1830 ms 45124 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 170 ms 856 KB Output is correct
11 Correct 61 ms 856 KB Output is correct
12 Correct 12 ms 1112 KB Output is correct
13 Correct 173 ms 860 KB Output is correct
14 Correct 73 ms 980 KB Output is correct
15 Correct 161 ms 1116 KB Output is correct
16 Correct 1727 ms 45132 KB Output is correct
17 Correct 1789 ms 44992 KB Output is correct
18 Correct 1840 ms 44988 KB Output is correct
19 Correct 1884 ms 44916 KB Output is correct
20 Correct 1839 ms 45132 KB Output is correct
21 Correct 1748 ms 45248 KB Output is correct
22 Correct 1790 ms 45128 KB Output is correct
23 Correct 1790 ms 45244 KB Output is correct
24 Correct 927 ms 45192 KB Output is correct
25 Correct 1391 ms 45128 KB Output is correct
26 Correct 1536 ms 44932 KB Output is correct
27 Correct 1143 ms 45124 KB Output is correct
28 Correct 1983 ms 45124 KB Output is correct
29 Correct 1823 ms 44992 KB Output is correct
30 Correct 1936 ms 45128 KB Output is correct
31 Correct 1935 ms 45132 KB Output is correct
32 Correct 1830 ms 45124 KB Output is correct
33 Execution timed out 4053 ms 45964 KB Time limit exceeded
34 Halted 0 ms 0 KB -