oj.uz

Submission #964661

# Submission time Handle Problem Language Result Execution time Memory
964661 2024-04-17T09:50:35 Z fve5 Werewolf (IOI18_werewolf) C++17
49 / 100
 400 ms 41528 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

class SegTree {
    vector<int> arr;
    int sz, s;

    int upper_bound_right(int l, int r, int d, int n, int nb, int ne) {
        if (nb >= r || ne <= l || arr[n] <= d) return sz;
        if (nb + 1 == ne) return nb;

        int lq = upper_bound_right(l, r, d, 2 * n, nb, (nb + ne) / 2);
        if (lq != sz) return lq;

        return upper_bound_right(l, r, d, 2 * n + 1, (nb + ne) / 2, ne);
    }

    int upper_bound_left(int l, int r, int d, int n, int nb, int ne) {
        if (nb >= r || ne <= l || arr[n] <= d) return -1;
        if (nb + 1 == ne) return nb;

        int rq = upper_bound_left(l, r, d, 2 * n + 1, (nb + ne) / 2, ne);
        if (rq != -1) return rq;

        return upper_bound_left(l, r, d, 2 * n, nb, (nb + ne) / 2);
    }

public:
    int upper_bound_left(int l, int r, int d) { return upper_bound_left(l, r, d, 1, 0, s); }
    int upper_bound_right(int l, int r, int d) { return upper_bound_right(l, r, d, 1, 0, s); }

    SegTree(int N, const vector<int> &a) : sz(N) {
        s = 1 << (int)ceil(log2(N));
        arr.resize(2 * s);

        for (int i = 0; i < N; i++)
            arr[i + s] = a[i];
        for (int i = s - 1; i > 0; i--)
            arr[i] = max(arr[2 * i], arr[2 * i + 1]);
    }
};

vector<int> solve_naive(
    int N, int M, int Q,
    vector<int> X, vector<int> Y,
    vector<int> S, vector<int> E,
    vector<int> L, vector<int> R
) {
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        vector<array<bool, 2>> visited(N);
        queue<pair<int, bool>> q;

        q.emplace(S[i], 0);
        while (!q.empty()) {
            auto [node, st] = q.front(); q.pop();
            if (visited[node][st]) continue;
            visited[node][st] = true;
            
            for (auto x: adj[node]) {
                if (!st && x >= L[i]) q.emplace(x, st);
                if (st && x <= R[i]) q.emplace(x, st);
            }

            if (!st && L[i] <= node && node <= R[i]) q.emplace(node, 1);
        }

        ans[i] = visited[E[i]][1];
    }

    return ans;
}

vector<int> solve_line(
    int N, int M, int Q,
    vector<int> X, vector<int> Y,
    vector<int> S, vector<int> E,
    vector<int> L, vector<int> R
) {
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    int curr = find_if(adj.begin(), adj.end(), [](const vector<int> &arr) {
        return arr.size() == 1;
    }) - adj.begin();

    vector<int> line;
    line.push_back(curr);

    int old = -1;
    for (int i = 0; i < N - 1; i++) {
        curr = adj[curr][adj[curr][0] == old];
        old = line.back();
        line.push_back(curr);
    }

    vector<int> mline(N);
    transform(line.begin(), line.end(), mline.begin(), [](int x) { return  -x; });

    vector<int> pos_of(N);
    for (int i = 0; i < N; i++)
        pos_of[line[i]] = i;

    SegTree segtree(N, line), msegtree(N, mline);
    vector<int> ans(Q);

    for (int i = 0; i < Q; i++) {
        int l1 = msegtree.upper_bound_left(0, pos_of[S[i]] + 1, -L[i]);
        int r1 = msegtree.upper_bound_right(pos_of[S[i]], N, -L[i]);

        int l2 = segtree.upper_bound_left(0, pos_of[E[i]] + 1, R[i]);
        int r2 = segtree.upper_bound_right(pos_of[E[i]], N, R[i]);

        ans[i] = !((l2 >= r1 - 1) || (r2 <= l1 + 1));
    }

    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();
    int Q = S.size();

    if (N <= 3000 && M <= 6000 && Q <= 3000) {
        return solve_naive(N, M, Q, X, Y, S, E, L, R);
    }
    return solve_line(N, M, Q, X, Y, S, E, L, R);
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 400 ms 848 KB Output is correct
11 Correct 265 ms 836 KB Output is correct
12 Correct 18 ms 824 KB Output is correct
13 Correct 321 ms 852 KB Output is correct
14 Correct 220 ms 836 KB Output is correct
15 Correct 294 ms 956 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 32728 KB Output is correct
2 Correct 265 ms 32896 KB Output is correct
3 Correct 270 ms 32708 KB Output is correct
4 Correct 286 ms 32748 KB Output is correct
5 Correct 262 ms 32680 KB Output is correct
6 Correct 315 ms 32896 KB Output is correct
7 Correct 285 ms 32876 KB Output is correct
8 Correct 267 ms 32664 KB Output is correct
9 Correct 248 ms 32900 KB Output is correct
10 Correct 230 ms 32896 KB Output is correct
11 Correct 280 ms 32896 KB Output is correct
12 Correct 221 ms 32660 KB Output is correct
13 Correct 274 ms 32908 KB Output is correct
14 Correct 263 ms 32748 KB Output is correct
15 Correct 295 ms 32708 KB Output is correct
16 Correct 256 ms 32900 KB Output is correct
17 Correct 281 ms 32900 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 400 ms 848 KB Output is correct
11 Correct 265 ms 836 KB Output is correct
12 Correct 18 ms 824 KB Output is correct
13 Correct 321 ms 852 KB Output is correct
14 Correct 220 ms 836 KB Output is correct
15 Correct 294 ms 956 KB Output is correct
16 Correct 318 ms 32728 KB Output is correct
17 Correct 265 ms 32896 KB Output is correct
18 Correct 270 ms 32708 KB Output is correct
19 Correct 286 ms 32748 KB Output is correct
20 Correct 262 ms 32680 KB Output is correct
21 Correct 315 ms 32896 KB Output is correct
22 Correct 285 ms 32876 KB Output is correct
23 Correct 267 ms 32664 KB Output is correct
24 Correct 248 ms 32900 KB Output is correct
25 Correct 230 ms 32896 KB Output is correct
26 Correct 280 ms 32896 KB Output is correct
27 Correct 221 ms 32660 KB Output is correct
28 Correct 274 ms 32908 KB Output is correct
29 Correct 263 ms 32748 KB Output is correct
30 Correct 295 ms 32708 KB Output is correct
31 Correct 256 ms 32900 KB Output is correct
32 Correct 281 ms 32900 KB Output is correct
33 Incorrect 194 ms 41528 KB Output isn't correct
34 Halted 0 ms 0 KB -