oj.uz

Submission #778386

# Submission time Handle Problem Language Result Execution time Memory
778386 2023-07-10T09:04:41 Z IBory Werewolf (IOI18_werewolf) C++17
15 / 100
 143 ms 38500 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int SZ = 1 << 13;
int inv[SZ];

struct BIT {
    int T[SZ];
    void Update(int i, int v) {
        for (; i < SZ; i += i & -i) T[i] += v;
    }
    int Query(int L, int R) {
        int ret = 0; L--;
        for (; R; R -= R & -R) ret += T[R];
        for (; L; L -= L & -L) ret -= T[L];
        return ret;
    }
} T;

struct UFTree {
    int R[SZ], A[SZ], in[SZ], out[SZ], P[19][SZ], node, dn;
    vector<int> G[SZ];

    UFTree(int N, vector<pii>& E, int type) {
        iota(R, R + SZ, 0);
        node = N - 1;
        Construct(E, type);
        DFS(node);
    }

    int Find(int n) {
        if (n == R[n]) return n;
        return R[n] = Find(R[n]);
    }

    bool Union(int a, int b, int c) {
        R[a] = c, R[b] = c;
        return 1;
    }

    void Construct(vector<pii>& E, int type) {
        for (int i = 0; i <= node; ++i) A[i] = i;
        for (auto [a, b] : E) {
            a = Find(a), b = Find(b);
            if (a != b) {
                P[0][a] = P[0][b] = ++node;
                Union(a, b, node);
                G[node].push_back(a);
                G[node].push_back(b);
                A[node] = (type == 1 ? max(A[a], A[b]) : min(A[a], A[b]));
            }
        }

        P[0][node] = node;
        for (int n = 1; n < 19; ++n) for (int i = 0; i <= node; ++i) {
            P[n][i] = P[n - 1][P[n - 1][i]];
        }
    }

    void DFS(int cur) {
        in[cur] = ++dn;
        for (int next : G[cur]) DFS(next);
        out[cur] = dn;
    }
};

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<pii> Eord[2];
    for (int i = 0; i < M; ++i) {
        Eord[0].emplace_back(X[i], Y[i]);
        Eord[1].emplace_back(X[i], Y[i]);
    }

    sort(Eord[0].begin(), Eord[0].end(), [&](pii& a, pii& b) {
        return max(a.first, a.second) < max(b.first, b.second);
    });
    sort(Eord[1].begin(), Eord[1].end(), [&](pii& a, pii& b) {
        return min(a.first, a.second) > min(b.first, b.second);
    });

    UFTree T1(N, Eord[1], 0);
    UFTree T2(N, Eord[0], 1);
    vector<int> ans(Q);
    vector<pair<pii, pair<pii, int>>> Qord;
    for (int i = 0; i < Q; ++i) {
        int s = S[i], e = E[i];
        for (int n = 18; n >= 0; --n) {
            if (L[i] <= T1.A[T1.P[n][s]]) s = T1.P[n][s];
            if (T2.A[T2.P[n][e]] <= R[i]) {
                e = T2.P[n][e];
            }
        }
        pii r = {T2.in[e], T2.out[e]};
        Qord.emplace_back(pii{T1.in[s], -1}, pair<pii, int>{r, i});
        Qord.emplace_back(pii{T1.out[s], 1}, pair<pii, int>{r, i});
    }
    pii dummy = {0, 0};
    for (int i = 0; i < N; ++i) Qord.emplace_back(pii{T1.in[i], 0}, pair<pii, int>{dummy, Q});

    sort(Qord.begin(), Qord.end());
    for (int i = 0; i < N; ++i) inv[T1.in[i]] = T2.in[i];
    for (auto [p1, p2] : Qord) {
        auto [x, type] = p1;
        auto [p3, qn] = p2;
        auto [l, r] = p3;
        if (type == -1) ans[qn] -= T.Query(l, r);
        else if (type == 0) T.Update(inv[x], 1);
        else ans[qn] += T.Query(l, r);
    }
    
    for (int& n : ans) n = n > 0;
    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2132 KB Output is correct
2 Correct 1 ms 2096 KB Output is correct
3 Correct 1 ms 2100 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 1 ms 2132 KB Output is correct
6 Correct 1 ms 2132 KB Output is correct
7 Correct 1 ms 2132 KB Output is correct
8 Correct 1 ms 2132 KB Output is correct
9 Correct 2 ms 2100 KB Output is correct
10 Correct 6 ms 3128 KB Output is correct
11 Correct 6 ms 3124 KB Output is correct
12 Correct 6 ms 3028 KB Output is correct
13 Correct 6 ms 3104 KB Output is correct
14 Correct 6 ms 3124 KB Output is correct
15 Correct 7 ms 3160 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 143 ms 38500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2132 KB Output is correct
2 Correct 1 ms 2096 KB Output is correct
3 Correct 1 ms 2100 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 1 ms 2132 KB Output is correct
6 Correct 1 ms 2132 KB Output is correct
7 Correct 1 ms 2132 KB Output is correct
8 Correct 1 ms 2132 KB Output is correct
9 Correct 2 ms 2100 KB Output is correct
10 Correct 6 ms 3128 KB Output is correct
11 Correct 6 ms 3124 KB Output is correct
12 Correct 6 ms 3028 KB Output is correct
13 Correct 6 ms 3104 KB Output is correct
14 Correct 6 ms 3124 KB Output is correct
15 Correct 7 ms 3160 KB Output is correct
16 Runtime error 143 ms 38500 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -