oj.uz

Submission #897806

# Submission time Handle Problem Language Result Execution time Memory
897806 2024-01-03T17:44:59 Z box Amusement Park (JOI17_amusement_park) C++17
10 / 100
 20 ms 4416 KB 
#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;
        for (int i = 0; i < N; i++) MessageBoard(i, color[i]);
    }
}

#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;
        i64 X = 0;
        while (dist[P] != 0) {
            P = par[P];
            int x = Move(P);
            if (dist[P] == 0) X |= i64(x) << index[P];
        }
        vector<vi> adj(N);
        for (auto [i, j] : edges) 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);
        auto make = [&](auto make, int i) -> void {
            for (int j : adj[i]) {
                X |= i64(Move(j)) << index[j];
                make(make, j);
                if (!has[j]) Move(i);
            }
        };
        make(make, P);
        return X;
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1040 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3644 KB Output is correct
2 Incorrect 19 ms 3636 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 788 KB Output is correct
2 Correct 0 ms 800 KB Output is correct
3 Correct 0 ms 800 KB Output is correct
4 Correct 2 ms 1188 KB Output is correct
5 Correct 2 ms 1088 KB Output is correct
6 Correct 3 ms 1088 KB Output is correct
7 Correct 2 ms 1348 KB Output is correct
8 Correct 2 ms 1348 KB Output is correct
9 Correct 9 ms 3152 KB Output is correct
10 Correct 9 ms 3144 KB Output is correct
11 Correct 9 ms 3148 KB Output is correct
12 Correct 1 ms 796 KB Output is correct
13 Correct 0 ms 784 KB Output is correct
14 Correct 0 ms 800 KB Output is correct
15 Correct 0 ms 792 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3652 KB Output is correct
2 Correct 18 ms 3664 KB Output is correct
3 Correct 18 ms 3656 KB Output is correct
4 Runtime error 14 ms 4416 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3640 KB Output is correct
2 Correct 20 ms 3644 KB Output is correct
3 Correct 18 ms 3804 KB Output is correct
4 Runtime error 12 ms 4416 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -