oj.uz

Submission #494820

# Submission time Handle Problem Language Result Execution time Memory
494820 2021-12-16T18:08:17 Z dxz05 Werewolf (IOI18_werewolf) C++14
34 / 100
 579 ms 78696 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 4e5 + 3e2;

vector<int> g[MAXN];

vector<int> vec, ord;
void dfs(int v, int p){
    ord[v] = vec.size();
    vec.push_back(v);
    for (int u : g[v]){
        if (u != p) dfs(u, v);
    }
}

int Tmin[MAXN][20], Tmax[MAXN][20], Log[MAXN];

int get_min(int l, int r){
    if (l > r) return 1e9;
    int j = Log[r - l + 1];
    return min(Tmin[l][j], Tmin[r - (1 << j) + 1][j]);
}

int get_max(int l, int r){
    if (l > r) return -1e9;
    int j = Log[r - l + 1];
    return max(Tmax[l][j], Tmax[r - (1 << j) + 1][j]);
}

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

    if (M != N - 1) return A;

    for (int i = 0; i < M; i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    ord.resize(N);

    for (int i = 0; i < N; i++){
        if (g[i].size() == 1){
            dfs(i, i);
            break;
        }
    }

    Log[1] = 0;
    for (int i = 0; i < MAXN; i++){
        if (i < N) Tmin[i][0] = Tmax[i][0] = vec[i];
        if (i > 1) Log[i] = Log[i / 2] + 1;
    }

    for (int j = 1; j < 20; j++){
        for (int i = 0; i < N; i++){
            if (i + (1 << j) - 1 < N){
                Tmin[i][j] = min(Tmin[i][j - 1], Tmin[i + (1 << (j - 1))][j - 1]);
                Tmax[i][j] = max(Tmax[i][j - 1], Tmax[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    for (int i = 0; i < Q; i++){
        S[i] = ord[S[i]], E[i] = ord[E[i]];

        if (S[i] < E[i]){
            int l = S[i], r = N - 1;
            while (l <= r){
                int mid = (l + r) >> 1;
                if (get_min(S[i], mid) >= L[i]) l = mid + 1; else
                    r = mid - 1;
            }

            int x = l - 1;

            l = 0, r = E[i];
            while (l <= r){
                int mid = (l + r) >> 1;
                if (get_max(mid, E[i]) <= R[i]) r = mid - 1; else
                    l = mid + 1;
            }

            int y = r + 1;

            A[i] = x >= y;

        } else {
            int l = 0, r = S[i];
            while (l <= r){
                int mid = (l + r) >> 1;
                if (get_min(mid, S[i]) >= L[i]) r = mid - 1; else
                    l = mid + 1;
            }

            int x = r + 1;

            l = E[i], r = N - 1;
            while (l <= r){
                int mid = (l + r) >> 1;
                if (get_max(E[i], mid) <= R[i]) l = mid + 1; else
                    r = mid - 1;
            }

            int y = l - 1;

            A[i] = x <= y;
        }

    }

    return A;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9676 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 503 ms 70208 KB Output is correct
2 Correct 526 ms 78644 KB Output is correct
3 Correct 549 ms 78620 KB Output is correct
4 Correct 536 ms 78508 KB Output is correct
5 Correct 523 ms 78512 KB Output is correct
6 Correct 491 ms 78668 KB Output is correct
7 Correct 566 ms 78560 KB Output is correct
8 Correct 460 ms 78672 KB Output is correct
9 Correct 362 ms 78504 KB Output is correct
10 Correct 329 ms 78496 KB Output is correct
11 Correct 374 ms 78496 KB Output is correct
12 Correct 351 ms 78512 KB Output is correct
13 Correct 579 ms 78628 KB Output is correct
14 Correct 529 ms 78500 KB Output is correct
15 Correct 535 ms 78536 KB Output is correct
16 Correct 546 ms 78684 KB Output is correct
17 Correct 563 ms 78696 KB Output is correct

Subtask #4
0 / 51.0

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