Submission #1370302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370302		husseinjuanda	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	19 ms	5444 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    const int K = 60;

    vector<vector<int>> g, tree;
    vector<int> ord, col;
    vector<array<int, K>> box;
    vector<int> mark;
    int timer_;

    void build_tree(int u, vector<int> &vis) {
        vis[u] = 1;
        ord.push_back(u);

        for (int v : g[u]) {
            if (vis[v]) continue;
            tree[u].push_back(v);
            tree[v].push_back(u);
            build_tree(v, vis);
        }
    }

    int find_leaf(const array<int, K> &cur, int ban) {
        ++timer_;
        for (int x : cur) mark[x] = timer_;

        for (int x : cur) {
            if (x == ban) continue;

            int deg = 0;
            for (int y : tree[x]) {
                if (mark[y] == timer_) deg++;
            }

            if (deg == 1) return x;
        }

        return -1;
    }

    void prepare(int N, int M, int A[], int B[]) {
        g.assign(N, {});
        tree.assign(N, {});
        ord.clear();
        col.assign(N, -1);
        box.assign(N, {});
        mark.assign(N, 0);
        timer_ = 0;

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

        vector<int> vis(N, 0);
        build_tree(0, vis);

        array<int, K> base;
        for (int i = 0; i < K; i++) {
            base[i] = ord[i];
        }

        queue<int> q;

        for (int i = 0; i < K; i++) {
            int v = base[i];
            col[v] = i;
            box[v] = base;
            q.push(v);
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : tree[u]) {
                if (col[v] != -1) continue;

                int rem = find_leaf(box[u], u);

                box[v] = box[u];
                for (int i = 0; i < K; i++) {
                    if (box[v][i] == rem) {
                        box[v][i] = v;
                        break;
                    }
                }

                col[v] = col[rem];
                q.push(v);
            }
        }
    }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    prepare(N, M, A, B);

    for (int i = 0; i < N; i++) {
        int bit = (X >> col[i]) & 1LL;
        MessageBoard(i, bit);
    }
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    const int K = 60;

    vector<vector<int>> g, tree;
    vector<int> ord, col;
    vector<array<int, K>> box;
    vector<int> mark;
    int timer_;

    long long ans;

    void build_tree(int u, vector<int> &vis) {
        vis[u] = 1;
        ord.push_back(u);

        for (int v : g[u]) {
            if (vis[v]) continue;
            tree[u].push_back(v);
            tree[v].push_back(u);
            build_tree(v, vis);
        }
    }

    int find_leaf(const array<int, K> &cur, int ban) {
        ++timer_;
        for (int x : cur) mark[x] = timer_;

        for (int x : cur) {
            if (x == ban) continue;

            int deg = 0;
            for (int y : tree[x]) {
                if (mark[y] == timer_) deg++;
            }

            if (deg == 1) return x;
        }

        return -1;
    }

    void prepare(int N, int M, int A[], int B[]) {
        g.assign(N, {});
        tree.assign(N, {});
        ord.clear();
        col.assign(N, -1);
        box.assign(N, {});
        mark.assign(N, 0);
        timer_ = 0;

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

        vector<int> vis(N, 0);
        build_tree(0, vis);

        array<int, K> base;
        for (int i = 0; i < K; i++) {
            base[i] = ord[i];
        }

        queue<int> q;

        for (int i = 0; i < K; i++) {
            int v = base[i];
            col[v] = i;
            box[v] = base;
            q.push(v);
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : tree[u]) {
                if (col[v] != -1) continue;

                int rem = find_leaf(box[u], u);

                box[v] = box[u];
                for (int i = 0; i < K; i++) {
                    if (box[v][i] == rem) {
                        box[v][i] = v;
                        break;
                    }
                }

                col[v] = col[rem];
                q.push(v);
            }
        }
    }

    void dfs_read(int u, int p) {
        for (int v : tree[u]) {
            if (v == p) continue;
            if (mark[v] != timer_) continue;

            int val = Move(v);
            if (val) ans |= (1LL << col[v]);

            dfs_read(v, u);

            Move(u);
        }
    }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    prepare(N, M, A, B);

    ans = 0;
    if (V) ans |= (1LL << col[P]);

    ++timer_;
    for (int x : box[P]) mark[x] = timer_;

    dfs_read(P, -1);

    return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17