oj.uz

Submission #964653

# Submission time Handle Problem Language Result Execution time Memory
964653 2024-04-17T09:43:30 Z fve5 Werewolf (IOI18_werewolf) C++17
15 / 100
 383 ms 32900 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_right(l, r, d, 2 * n + 1, (nb + ne) / 2, ne);
        if (rq != -1) return rq;

        return upper_bound_right(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 r1 = msegtree.upper_bound_left(pos_of[S[i]], N, -L[i]);
        int l1 = msegtree.upper_bound_right(0, pos_of[S[i]] + 1, -L[i]);

        int r2 = segtree.upper_bound_left(pos_of[E[i]], N, R[i]);
        int l2 = segtree.upper_bound_right(0, pos_of[E[i]] + 1, 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 344 KB Output is correct
4 Correct 1 ms 344 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 344 KB Output is correct
8 Correct 1 ms 348 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 344 KB Output is correct
4 Correct 1 ms 344 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 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 383 ms 860 KB Output is correct
11 Correct 258 ms 824 KB Output is correct
12 Correct 17 ms 604 KB Output is correct
13 Correct 309 ms 856 KB Output is correct
14 Correct 207 ms 832 KB Output is correct
15 Correct 300 ms 956 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 32900 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 344 KB Output is correct
4 Correct 1 ms 344 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 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 383 ms 860 KB Output is correct
11 Correct 258 ms 824 KB Output is correct
12 Correct 17 ms 604 KB Output is correct
13 Correct 309 ms 856 KB Output is correct
14 Correct 207 ms 832 KB Output is correct
15 Correct 300 ms 956 KB Output is correct
16 Incorrect 201 ms 32900 KB Output isn't correct
17 Halted 0 ms 0 KB -