답안 #958250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958250 2024-04-05T08:28:59 Z Basexal Amusement Park (JOI17_amusement_park) C++17
컴파일 오류
0 ms 0 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);
        }
        CNT_ONCE = h[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 {
        fl = true;
        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;
    }
}

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:169:9: error: 'CNT_ONCE' was not declared in this scope
  169 |         CNT_ONCE = h[cur_v];
      |         ^~~~~~~~
Ioi.cpp:192:9: error: 'fl' was not declared in this scope
  192 |         fl = true;
      |         ^~