oj.uz

Submission #958252

# Submission time Handle Problem Language Result Execution time Memory
958252 2024-04-05T08:29:38 Z Basexal Amusement Park (JOI17_amusement_park) C++17
81 / 100
 22 ms 6732 KB 
#include "Joi.h"

#include <vector>
const int BITS = 60;

void dfs(int v, int& t, int mp, std::vector<int>& tin, std::vector<int>& used, std::vector<int>& p, const std::vector<std::vector<int>>& g, std::vector<std::vector<int>>& childs, std::vector<int>& sz) {
    tin[v] = t++;
    p[v] = mp;
    sz[v] = 1;
    if (t >= BITS) {
        t -= BITS;
    }
    used[v] = 1;
    for (auto& u : g[v]) {
        if (used[u] == 0) {
            childs[v].push_back(u);
            dfs(u, t, v, tin, used, p, g, childs, sz);
            sz[v] += sz[u];
        }
    }
}

void Joi(int N, int M, int A[], int B[], long long x, int T) {
    std::vector<std::vector<int>> g(N);
    for (int i = 0; i < M; ++i) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    std::vector<int> tin(N), used(N), p(N), sz(N);
    int t = 0;
    std::vector<std::vector<int>> childs(N);
    dfs(0, t, 0, tin, used, p, g, childs, sz);
    for (int i = 0; i < N; ++i) {
        MessageBoard(i, (x >> tin[i]) & 1);
    }
    return;
}

#include "Ioi.h"

#include <vector>

const int BITS = 60;
int Mov(int u) {
    return Move(u);
}

void dfs(int v, int& t, int mp, std::vector<int>& tin, std::vector<int>& used, std::vector<int>& p, const std::vector<std::vector<int>>& g, std::vector<std::vector<int>>& childs, std::vector<int>& sz) {
    tin[v] = t++;
    p[v] = mp;
    sz[v] = 1;
    if (t >= BITS) {
        t -= BITS;
    }
    used[v] = 1;
    for (auto& u : g[v]) {
        if (used[u] == 0) {
            childs[v].push_back(u);
            dfs(u, t, v, tin, used, p, g, childs, sz);
            sz[v] += sz[u];
        }
    }
}

void dfs_down(int v, long long val, long long& ans, const std::vector<std::vector<int>>& childs, std::vector<int>& getted, const std::vector<int>& tin) {
    getted[tin[v]] += 1;
    getted[tin[v] + BITS] += 1;
    ans += val << tin[v];
    for (auto& u : childs[v]) {
        if (getted[tin[u]] == 0) {
            long long new_val = Mov(u);
            dfs_down(u, new_val, ans, childs, getted, tin);
            Mov(v);
        }
    }
}

void dfs2(int v, int& t, std::vector<int>& tin, std::vector<int>& tout, const std::vector<std::vector<int>>& childs) {
    tin[v] = t++;
    for (auto& u : childs[v]) {
        dfs2(u, t, tin, tout, childs);
    }
    tout[v] = t - 1;
}

void dfs_twice(int v, long long val, long long& ans, int l, int r, int ql, int qr, const std::vector<std::vector<int>>& childs, const std::vector<int>& tin2, const std::vector<int>& tout2, const std::vector<int>& tin, std::vector<int>& getted) {
    ans += val << tin[v];
    getted[tin2[v]] += 1;
    for (auto& u : childs[v]) {
        int qql = tin2[u], qqr = std::min(tout2[u], qr);
        if (qql > qr) {
            break;
        }
        if ((l <= qql && qqr <= r) || (l <= qql + BITS && qqr + BITS <= r)) {
            continue;
        }
        long long new_val = Mov(u);
        dfs_twice(u, new_val, ans, l, r, qql, qqr, childs, tin2, tout2, tin, getted);
        Mov(v);
    }
}

void dfs_once(int v, long long val, long long& ans, int l, int r, int ql, int qr, const std::vector<std::vector<int>>& childs, const std::vector<int>& tin2, const std::vector<int>& tout2, const std::vector<int>& tin, std::vector<int>& getted) {
    if (getted[tin2[v]] == 0) {
        ans += val << tin[v];
        getted[tin2[v]] += 1;
    }
    int last = -1;
    for (auto& u : childs[v]) {
        int qql = tin2[u], qqr = std::min(tout2[u], qr);
        if (qql > qr) {
            break;
        }
        if ((l <= qql && qqr <= r) || (l <= qql + BITS && qqr + BITS <= r)) {
            continue;
        }
        if ((qql <= r && r < qqr) || (qql + BITS <= r && r < qqr + BITS)) {
            last = u;
        } else {
            long long new_val = Mov(u);
            dfs_twice(u, new_val, ans, l, r, ql, qr, childs, tin2, tout2, tin, getted);
            Mov(v);
        }
    }
    if (last != -1) {
        int u = last;
        long long new_val = Mov(u);
        int qql = tin2[u], qqr = std::min(tout2[u], qr);
        dfs_once(u, new_val, ans, l, r, qql, qqr, childs, tin2, tout2, tin, getted);
    }
}

void get_h(int v, int qr, const std::vector<std::vector<int>>& childs, std::vector<int>& h, std::vector<int>& tin2) {
    h[v] = 0;
    for (auto& u : childs[v]) {
        if (tin2[u] > qr) {
            break;
        }
        get_h(u, qr, childs, h, tin2);
        h[v] = std::max(h[v], h[u] + 1);
    }
}

int get_str(int v, const std::vector<std::vector<int>>& childs, const std::vector<int>& sz, const std::vector<int>& p, std::vector<int>& h) {
    int cur_p = -1, k = 0;
    while (sz[v] < BITS) {
        cur_p = v;
        v = p[v];
        k++;
    }
    if (cur_p == -1) {
        return -1;
    }
    std::vector<int> tin2(h.size()), tout2(h.size());
    int t = 0;
    dfs2(v, t, tin2, tout2, childs);
    get_h(v, tin2[v] + BITS - 1, childs, h, tin2);
    if (h[v] < 10) {
        return -1;
    } else {
        return 1;
    }
}

void dfs_ans(int v, int qr, long long val, long long& ans, std::vector<int>& h, std::vector<int>& tin2, std::vector<int>& getted, const std::vector<std::vector<int>>& childs) {
    ans += val << tin2[v] % BITS;
    int last = -1;
    for (auto& u : childs[v]) {
        if (tin2[u] > qr) {
            break;
        }
        if (h[u] == h[v] - 1 && last == -1) {
            last = u;
        } else {
            long long new_val = Mov(u);
            dfs_ans(u, qr, new_val, ans, h, tin2, getted, childs);
            Mov(v);
        }
    }
    if (last != -1) {
        long long new_val = Mov(last);
        dfs_ans(last, qr, new_val, ans, h, tin2, getted, childs);
    }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    std::vector<std::vector<int>> g(N);
    for (int i = 0; i < M; ++i) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    std::vector<int> tin(N), used(N), p(N), sz(N), h(N);
    int t = 0;
    std::vector<std::vector<int>> childs(N);
    dfs(0, t, 0, tin, used, p, g, childs, sz);
    int str = get_str(P, childs, sz, p, h);
    std::vector<int> getted(2 * BITS);
    if (str != 0) {
        int cur_v = P, cur_p = -1;
        long long cur_val = V, ans = 0;
        while (sz[cur_v] < BITS) {
            dfs_down(cur_v, cur_val, ans, childs, getted, tin);
            cur_p = cur_v;
            cur_v = p[cur_v];
            cur_val = Mov(cur_v);
        }
        if (cur_p != -1) {
            int k = tin[cur_v];
            int l = tin[cur_p];
            if (l < k) {
                l += BITS;
            }
            std::vector<int> tin2(N), tout2(N);
            t = k;
            dfs2(cur_v, t, tin2, tout2, childs);
            int r = l + tout2[cur_p] - tin2[cur_p];
            dfs_once(cur_v, cur_val, ans, l, r, k, k + BITS - 1, childs, tin2, tout2, tin, getted);
        } else {
            int k = tin[cur_v];
            int l = -1;
            std::vector<int> tin2(N), tout2(N);
            t = k;
            dfs2(cur_v, t, tin2, tout2, childs);
            int r = -1;
            dfs_twice(cur_v, cur_val, ans, l, r, k, k + BITS - 1, childs, tin2, tout2, tin, getted);
        }
        return ans;
    } else {
        int cur_v = P;
        long long cur_val = V, ans = 0;
        while (sz[cur_v] < BITS) {
            cur_v = p[cur_v];
            cur_val = Mov(cur_v);
        }
        std::vector<int> tin2(N), tout2(N);
        t = tin[cur_v];
        dfs2(cur_v, t, tin2, tout2, childs);
        dfs_ans(cur_v, tin[cur_v] + BITS - 1, cur_val, ans, h, tin2, getted, childs);
        return ans;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 784 KB Output is correct
2 Correct 0 ms 796 KB Output is correct
3 Correct 1 ms 792 KB Output is correct
4 Correct 0 ms 784 KB Output is correct
5 Correct 0 ms 796 KB Output is correct
6 Correct 1 ms 1036 KB Output is correct
7 Correct 1 ms 800 KB Output is correct
8 Correct 1 ms 792 KB Output is correct
9 Correct 1 ms 800 KB Output is correct
10 Correct 1 ms 784 KB Output is correct
11 Correct 3 ms 1124 KB Output is correct
12 Correct 0 ms 1296 KB Output is correct
13 Correct 0 ms 788 KB Output is correct
14 Correct 1 ms 872 KB Output is correct
15 Correct 1 ms 788 KB Output is correct
16 Correct 1 ms 792 KB Output is correct
17 Correct 1 ms 800 KB Output is correct
18 Correct 1 ms 792 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6200 KB Output is correct
2 Correct 19 ms 6164 KB Output is correct
3 Correct 19 ms 6168 KB Output is correct
4 Correct 12 ms 3656 KB Output is correct
5 Correct 15 ms 5276 KB Output is correct
6 Correct 12 ms 4728 KB Output is correct
7 Correct 11 ms 4672 KB Output is correct
8 Correct 14 ms 4664 KB Output is correct
9 Correct 14 ms 4936 KB Output is correct
10 Correct 12 ms 3772 KB Output is correct
11 Correct 12 ms 3652 KB Output is correct
12 Correct 11 ms 3700 KB Output is correct
13 Correct 9 ms 3620 KB Output is correct
14 Correct 10 ms 3640 KB Output is correct
15 Correct 12 ms 4156 KB Output is correct
16 Correct 11 ms 4156 KB Output is correct
17 Correct 11 ms 3908 KB Output is correct
18 Correct 11 ms 3880 KB Output is correct
19 Correct 11 ms 4032 KB Output is correct
20 Correct 10 ms 5024 KB Output is correct
21 Correct 12 ms 5020 KB Output is correct
22 Correct 15 ms 4424 KB Output is correct
23 Correct 14 ms 4764 KB Output is correct
24 Correct 11 ms 4676 KB Output is correct
25 Correct 13 ms 4684 KB Output is correct
26 Correct 13 ms 4672 KB Output is correct
27 Correct 13 ms 4672 KB Output is correct
28 Correct 12 ms 4852 KB Output is correct
29 Correct 13 ms 4392 KB Output is correct
30 Correct 11 ms 4652 KB Output is correct
31 Correct 0 ms 784 KB Output is correct
32 Correct 1 ms 788 KB Output is correct
33 Correct 1 ms 1396 KB Output is correct
34 Correct 1 ms 876 KB Output is correct
35 Correct 1 ms 800 KB Output is correct
36 Correct 0 ms 796 KB Output is correct
37 Correct 1 ms 864 KB Output is correct
38 Correct 0 ms 784 KB Output is correct
39 Correct 1 ms 780 KB Output is correct
40 Correct 1 ms 780 KB Output is correct
41 Correct 0 ms 780 KB Output is correct
42 Correct 1 ms 780 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 784 KB Output is correct
2 Correct 0 ms 932 KB Output is correct
3 Correct 0 ms 784 KB Output is correct
4 Correct 3 ms 1852 KB Output is correct
5 Correct 2 ms 1860 KB Output is correct
6 Correct 4 ms 1852 KB Output is correct
7 Correct 2 ms 1864 KB Output is correct
8 Correct 2 ms 1848 KB Output is correct
9 Correct 11 ms 6716 KB Output is correct
10 Correct 9 ms 6732 KB Output is correct
11 Correct 9 ms 6724 KB Output is correct
12 Correct 1 ms 784 KB Output is correct
13 Correct 1 ms 796 KB Output is correct
14 Correct 1 ms 784 KB Output is correct
15 Correct 0 ms 780 KB Output is correct

Subtask #4
53.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6196 KB Output is correct
2 Partially correct 20 ms 6188 KB Partially correct
3 Correct 22 ms 6172 KB Output is correct
4 Correct 13 ms 3648 KB Output is correct
5 Correct 15 ms 5900 KB Output is correct
6 Correct 12 ms 4680 KB Output is correct
7 Correct 11 ms 4656 KB Output is correct
8 Correct 11 ms 4424 KB Output is correct
9 Correct 11 ms 4680 KB Output is correct
10 Correct 9 ms 3660 KB Output is correct
11 Correct 10 ms 3660 KB Output is correct
12 Correct 9 ms 3628 KB Output is correct
13 Correct 10 ms 3632 KB Output is correct
14 Correct 11 ms 3896 KB Output is correct
15 Correct 11 ms 4160 KB Output is correct
16 Correct 12 ms 4164 KB Output is correct
17 Correct 11 ms 3904 KB Output is correct
18 Correct 11 ms 3908 KB Output is correct
19 Correct 11 ms 3912 KB Output is correct
20 Correct 10 ms 5192 KB Output is correct
21 Correct 9 ms 5192 KB Output is correct
22 Correct 11 ms 4672 KB Output is correct
23 Correct 11 ms 4672 KB Output is correct
24 Correct 12 ms 4680 KB Output is correct
25 Correct 11 ms 4820 KB Output is correct
26 Correct 11 ms 4684 KB Output is correct
27 Correct 13 ms 5156 KB Output is correct
28 Correct 11 ms 4680 KB Output is correct
29 Correct 13 ms 4588 KB Output is correct
30 Correct 11 ms 4660 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6176 KB Output is correct
2 Correct 18 ms 6164 KB Output is correct
3 Correct 19 ms 6168 KB Output is correct
4 Correct 12 ms 3640 KB Output is correct
5 Correct 12 ms 6220 KB Output is correct
6 Correct 13 ms 4676 KB Output is correct
7 Correct 13 ms 4748 KB Output is correct
8 Correct 13 ms 4932 KB Output is correct
9 Correct 12 ms 4680 KB Output is correct
10 Correct 9 ms 3664 KB Output is correct
11 Correct 9 ms 3656 KB Output is correct
12 Correct 10 ms 3632 KB Output is correct
13 Correct 10 ms 3632 KB Output is correct
14 Correct 11 ms 3632 KB Output is correct
15 Incorrect 12 ms 4168 KB Output isn't correct
16 Halted 0 ms 0 KB -