Submission #897822

#	Time	Username	Problem	Language	Result	Execution time	Memory
897822		box	Amusement Park (JOI17_amusement_park)	C++17	10 / 100	18 ms	3816 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>

using std::cerr, std::endl;

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef std::vector<int> vi;

namespace {

vi uf;

int find(int i) {
    return uf[i] == i ? i : uf[i] = find(uf[i]);
}
bool join(int i, int j) {
    i = find(i), j = find(j);
    if (i == j) return 0;
    uf[i] = uf[j] = i;
    return 1;
}

}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    uf.resize(N);
    std::iota(all(uf), 0);
    std::vector<vi> adj(N);
    for (int i = 0; i < M; i++) if (join(A[i], B[i])) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    vi dist(N, -1);
    vi parent(N, -1);
    auto bfs = [&](int i) {
        std::fill(all(dist), -1);
        std::queue<int> qu;
        dist[i] = 0; qu.push(i);
        while (sz(qu)) {
            int i = qu.front(); qu.pop();
            for (int j : adj[i]) if (dist[j] == -1) {
                dist[j] = dist[i] + 1;
                parent[j] = i;
                qu.push(j);
            }
        }
    };
    bfs(0);
    int u = std::max_element(all(dist)) - std::begin(dist);
    bfs(u);
    int v = std::max_element(all(dist)) - std::begin(dist);
    if (dist[v] >= 59) {
        for (int i = 0; i < N; i++)
            MessageBoard(i, X >> (dist[i] % 60) & 1);
    } else {
        vi par = parent;
        vi diameter = {v};
        while (diameter.back() != u) diameter.push_back(par[diameter.back()]);
        std::fill(all(dist), -1);
        vi qu = diameter;
        for (int x : diameter) dist[x] = 0;
        for (int i = 0; i < sz(qu); i++) {
            int u = qu[i];
            for (int v : adj[u]) if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                qu.push_back(v);
            }
        }
        assert(sz(qu) >= 60);
        qu.resize(60);
        vi color(N);
        for (int i = 0; i < 60; i++) {
            color[qu[i]] = X >> i & 1;
            bug(qu[i], i, X >> i & 1);
        }
        for (int i = 0; i < N; i++) MessageBoard(i, color[i]);
    }
}

Ioi

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

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;

namespace {

vi uf;

int find(int i) {
    return uf[i] == i ? i : uf[i] = find(uf[i]);
}
bool join(int i, int j) {
    i = find(i), j = find(j);
    if (i == j) return 0;
    uf[i] = uf[j] = i;
    return 1;
}

}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    uf.resize(N);
    iota(all(uf), 0);
    vector<vi> adj(N);
    for (int i = 0; i < M; i++) if (join(A[i], B[i])) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    vi dist(N, -1);
    vi parent(N, -1);
    vi child(N, -1);
    auto bfs = [&](int i) {
        fill(all(dist), -1);
        queue<int> qu;
        dist[i] = 0; qu.push(i);
        while (sz(qu)) {
            int i = qu.front(); qu.pop();
            for (int j : adj[i]) if (dist[j] == -1) {
                child[i] = j;
                dist[j] = dist[i] + 1;
                parent[j] = i;
                qu.push(j);
            }
        }
    };
    bfs(0);
    int u = max_element(all(dist)) - begin(dist);
    bfs(u);
    int v = max_element(all(dist)) - begin(dist);
    auto save = dist;
    if (dist[v] >= 59) {
        i64 X = i64(V) << (dist[P] % 60);
        if (dist[P] >= 59) {
            for (int it = 0; it < 59; it++) {
                P = parent[P];
                X |= i64(Move(P)) << (dist[P] % 60);
            }
        } else {
            while (P != u) {
                P = parent[P];
                X |= i64(Move(P)) << (dist[P] % 60);
            }
            for (int it = 0; it < 59; it++) {
                P = child[P];
                X |= i64(Move(P)) << (dist[P] % 60);
            }
        }
        return X;
    } else {
        vi diameter = {v};
        vector<pi> edges;
        vi par = parent;
        while (diameter.back() != u) {
            int v = diameter.back();
            edges.push_back({v, par[v]});
            diameter.push_back(par[v]);
        }
        fill(all(par), -1);
        fill(all(dist), -1);
        vi qu = diameter;
        for (int x : diameter) dist[x] = 0;
        for (int i = 0; i < sz(qu); i++) {
            int u = qu[i];
            for (int v : adj[u]) if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                par[v] = u;
                if (sz(qu) < 60)
                    edges.push_back({u, v});
                qu.push_back(v);
            }
        }
        assert(sz(qu) >= 60);
        vi index(N, -1);
        for (int i = 0; i < 60; i++) {
            index[qu[i]] = i;
            // bug(qu[i], i);
        }
        i64 X = 0;
        if (dist[P] == 0) {
            X |= i64(V) << index[P];
        }
        while (dist[P] != 0) {
            P = par[P];
            assert(~P);
            int x = Move(P);
            if (dist[P] == 0) {
                bug(x, index[P]);
                X |= i64(x) << index[P];
            }
            bug(P, dist[P]);
        }
        assert(sz(edges) == 59);
        vector<vi> adj(N);
        for (auto [i, j] : edges) {
            if (i == 5 || j == 5) bug(i, j);
            adj[i].push_back(j), adj[j].push_back(i);
        }
        int last = save[P] * 2 > save[v] ? u : v;
        vector<bool> has(N);
        auto dfs = [&](auto dfs, int i) -> bool {
            has[i] = i == last; int who = -1;
            for (int j : adj[i]) {
                adj[j].erase(find(all(adj[j]), i));
                if (dfs(dfs, j)) {
                    has[i] = 1;
                    who = j;
                }
            }
            if (has[i] && sz(adj[i])) {
                assert(~who);
                int pos = find(all(adj[i]), who) - begin(adj[i]);
                swap(adj[i][pos], adj[i].back());
            }
            return has[i];
        };
        dfs(dfs, P);
        int cnt = 0;
        i64 Y = 0;
        bug(P);
        auto make = [&](auto make, int i) -> void {
            ++cnt;
            for (int j : adj[i]) {
                bug(j, index[j]);
                Y |= i64(1) << index[j];
                int v = Move(j);
                X |= i64(v) << index[j];
                // if (v) bug(j, index[j]);
                make(make, j);
                if (!has[j]) Move(i);
            }
        };
        make(make, P);
        bug(cnt);
        bug(Y);
        return X;
    }
}

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