oj.uz

Submission #964660

# Submission time Handle Problem Language Result Execution time Memory
964660 2024-04-17T09:50:02 Z fve5 Werewolf (IOI18_werewolf) C++17
34 / 100
 356 ms 41312 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
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 32712 KB Output is correct
2 Correct 274 ms 41308 KB Output is correct
3 Correct 268 ms 41244 KB Output is correct
4 Correct 290 ms 41304 KB Output is correct
5 Correct 249 ms 41160 KB Output is correct
6 Correct 356 ms 41092 KB Output is correct
7 Correct 273 ms 41308 KB Output is correct
8 Correct 267 ms 41312 KB Output is correct
9 Correct 209 ms 41160 KB Output is correct
10 Correct 246 ms 41140 KB Output is correct
11 Correct 277 ms 41296 KB Output is correct
12 Correct 251 ms 41200 KB Output is correct
13 Correct 246 ms 41136 KB Output is correct
14 Correct 238 ms 41148 KB Output is correct
15 Correct 305 ms 41196 KB Output is correct
16 Correct 251 ms 41072 KB Output is correct
17 Correct 282 ms 41304 KB Output is correct

Subtask #4
0 / 51.0

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