oj.uz

Submission #964655

# Submission time Handle Problem Language Result Execution time Memory
964655 2024-04-17T09:44:03 Z fve5 Werewolf (IOI18_werewolf) C++17
0 / 100
 236 ms 32656 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
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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