oj.uz

Submission #599701

# Submission time Handle Problem Language Result Execution time Memory
599701 2022-07-19T19:14:18 Z skittles1412 Werewolf (IOI18_werewolf) C++17
34 / 100
 542 ms 94120 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using vi = vector<int>;

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

template <bool mn>
struct ST {
    static int op(int x, int y) {
        if (mn) {
            return min(x, y);
        } else {
            return max(x, y);
        }
    }

    int n;
    vector<vector<int>> v;

    ST(const vector<int>& arr) : n(sz(arr)), v(__lg(n) + 2, vector<int>(n)) {
        v[0] = arr;
        for (int i = 1; (1 << i) <= n; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                v[i][j] = op(v[i - 1][j], v[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    int query(int l, int r) {
        int k = __lg(r - l + 1);
        return op(v[k][l], v[k][r - (1 << k) + 1]);
    }
};

template <typename T>
T reversed(T t) {
    reverse(begin(t), end(t));
    return t;
}

struct Solver {
    int n;
    vector<int> arr, iarr;
    ST<true> mn;
    ST<false> mx;

    Solver(const vector<int>& arr): n(sz(arr)), arr(arr), iarr(n), mn(arr), mx(arr) {
        for (int i = 0; i < n; i++) {
            iarr[arr[i]] = i;
        }
    }

    int solve(int src, int dest, int ql, int qr) {
        src = iarr[src];
        dest = iarr[dest];
        if (src > dest) {
            return -1;
        }
        int x1, x2;
        {
            int l = src, r = dest;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (mn.query(src, mid) >= ql) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            x1 = l;
        }
        {
            int l = src, r = dest;
            while (l < r) {
                int mid = (l + r) / 2;
                if (mx.query(mid, dest) <= qr) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            x2 = r;
        }
        return x1 >= x2;
    }
};

vi check_validity(int n, vi us, vi vs, vi qsrc, vi qdest, vi ql, vi qr) {
    int m = sz(us), q = sz(qsrc);
    vector<int> graph[n];
    for (int i = 0; i < m; i++) {
        graph[us[i]].push_back(vs[i]);
        graph[vs[i]].push_back(us[i]);
    }
    if (false && n <= 3000 && m <= 6000 && q <= 3000) {
        vector<int> ans(q);
        for (int qi = 0; qi < q; qi++) {
            int src = qsrc[qi], dest = qdest[qi], l = ql[qi], r = qr[qi];
            bool vis[n][2] {};
            vector<pair<int, int>> q;
            auto push = [&](int u, int t) -> void {
                if (!vis[u][t]) {
                    vis[u][t] = true;
                    q.emplace_back(u, t);
                }
            };
            push(src, 0);
            while (sz(q)) {
                auto [u, t] = q.back();
                q.pop_back();
                if (l <= u && u <= r && !t) {
                    push(u, 1);
                }
                for (auto& v : graph[u]) {
                    if ((!t && v >= l) || (t && v <= r)) {
                        push(v, t);
                    }
                }
            }
            ans[qi] = vis[dest][1];
        }
        return ans;
    }
    vector<int> arr;
    for (int i = 0; i < n; i++) {
        if (sz(graph[i]) == 1) {
            int prv = 0;
            while (sz(arr) < n) {
                arr.push_back(i);
                for (auto& a : graph[i]) {
                    prv ^= a;
                }
                swap(prv, i);
            }
            break;
        }
    }
    Solver s1(arr), s2(reversed(arr));
    vector<int> ans(q);
    for (int qi = 0; qi < q; qi++) {
        int src = qsrc[qi], dest = qdest[qi], l = ql[qi], r = qr[qi];
        int cans = s1.solve(src, dest, l, r);
        if (cans == -1) {
            cans = s2.solve(src, dest, l, r);
        }
        ans[qi] = cans;
    }
    return ans;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 86380 KB Output is correct
2 Correct 471 ms 94080 KB Output is correct
3 Correct 424 ms 94112 KB Output is correct
4 Correct 454 ms 94116 KB Output is correct
5 Correct 461 ms 94108 KB Output is correct
6 Correct 542 ms 94116 KB Output is correct
7 Correct 529 ms 94112 KB Output is correct
8 Correct 459 ms 94120 KB Output is correct
9 Correct 307 ms 94052 KB Output is correct
10 Correct 268 ms 94044 KB Output is correct
11 Correct 300 ms 94104 KB Output is correct
12 Correct 307 ms 94044 KB Output is correct
13 Correct 414 ms 94052 KB Output is correct
14 Correct 438 ms 94108 KB Output is correct
15 Correct 476 ms 94088 KB Output is correct
16 Correct 413 ms 94112 KB Output is correct
17 Correct 515 ms 94120 KB Output is correct

Subtask #4
0 / 51.0

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