oj.uz

Submission #667947

# Submission time Handle Problem Language Result Execution time Memory
667947 2022-12-02T12:03:23 Z bashkort Amusement Park (JOI17_amusement_park) C++17
10 / 100
 25 ms 5780 KB 
#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    struct DSU {
        vector<int> p;
        DSU() = default;
        DSU(int n) : p(n) {
            iota(p.begin(), p.end(), 0);
        }

        int leader(int x) {
            while (x != p[x]) x = p[x] = p[p[x]];
            return x;
        }

        bool unite(int x, int y) {
            x = leader(x), y = leader(y);
            if (p[y] == x) {
                return false;
            } else {
                return p[y] = x, true;
            }
        }
    };

    mt19937 rnd(228);
    vector<pair<int, int>> edges(M);
    for (int i = 0; i < M; ++i) {
        edges[i] = {A[i], B[i]};
    }
    shuffle(edges.begin(), edges.end(), rnd);
    vector<int> tin(N), par(N, -1);
    vector<vector<int>> g(N), adj(N);
    DSU d(N);
    for (int i = 0; i < M; ++i) {
        auto [a, b] = edges[i];
        if (d.unite(a, b)) {
            g[a].push_back(b);
            g[b].push_back(a);
        }
    }

    int timer = 0;
    function<void(int)> dfs = [&](int v) {
        tin[v] = timer++;
        sort(g[v].begin(), g[v].end());
        for (int to : g[v]) {
            if (to != par[v]) {
                par[to] = v;
                adj[v].push_back(to);
                dfs(to);
            }
        }
    };
    dfs(0);

    for (int i = 0; i < N; ++i) {
        MessageBoard(i, X >> (tin[i] % 60) & 1);
    }
}

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

using namespace std;
using ll = long long;


long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    struct DSU {
        vector<int> p;

        DSU() = default;

        DSU(int n) : p(n) {
            iota(p.begin(), p.end(), 0);
        }

        int leader(int x) {
            while (x != p[x]) x = p[x] = p[p[x]];
            return x;
        }

        bool unite(int x, int y) {
            x = leader(x), y = leader(y);
            if (p[y] == x) {
                return false;
            } else {
                return p[y] = x, true;
            }
        }
    };

    mt19937 rnd(228);
    vector<pair<int, int>> edges(M);
    for (int i = 0; i < M; ++i) {
        edges[i] = {A[i], B[i]};
    }
    shuffle(edges.begin(), edges.end(), rnd);
    vector<int> tin(N), par(N, -1), tout(N);
    vector<vector<int>> g(N), adj(N);
    DSU d(N);
    for (int i = 0; i < M; ++i) {
        auto [a, b] = edges[i];
        if (d.unite(a, b)) {
            g[a].push_back(b);
            g[b].push_back(a);
        }
    }

    int timer = 0;
    function<void(int)> dfs = [&](int v) {
        tin[v] = timer++;
        sort(g[v].begin(), g[v].end());
        for (int to: g[v]) {
            if (to != par[v]) {
                par[to] = v;
                adj[v].push_back(to);
                dfs(to);
            }
        }
        tout[v] = timer++;
    };
    dfs(0);
    int LOG = 60;
    vector<bool> used(N);
    vector<int> ans(LOG, -1);
    ans[tin[P] % LOG] = V;
    vector<int> last(N, -1);
    int x = P;
    auto any = [&](int l, int r) {
        if (l >= r) {
            return (r && find(ans.begin(), ans.begin() + r, -1) != (ans.begin() + r))
                   || (find(ans.begin() + l, ans.end(), -1) != ans.end());
        }
        return find(ans.begin() + l, ans.begin() + r, -1) != (ans.begin() + r);
    };
    while (any(0, LOG)) {
        used[x] = true;
        auto it = upper_bound(adj[x].begin(), adj[x].end(), last[x]);
        if (it == adj[x].end()) {
            it = adj[x].begin();
        }
        if (adj[x].empty() || used[*it]) {
            last[par[x]] = x;
            x = par[x];
            assert(x != -1);
            ans[tin[x] % LOG] = Move(x);
        } else {
            last[x] = *it;
            int to = *it;
            if (any(tin[to] % 60, tout[to] % 60)) {
                x = *it;
                ans[tin[x] % LOG] = Move(x);
            } else {
                adj[x].erase(lower_bound(adj[x].begin(), adj[x].end(), to));
            }
        }
    }

    ll X = 0;
    for (int i = 0; i < LOG; ++i) {
        assert(ans[i] != -1);
        X += ans[i] * (1LL << i);
    }

    return X;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4200 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 776 KB Output is correct
2 Correct 1 ms 648 KB Output is correct
3 Correct 0 ms 768 KB Output is correct
4 Correct 4 ms 1444 KB Output is correct
5 Correct 3 ms 1564 KB Output is correct
6 Correct 3 ms 1564 KB Output is correct
7 Correct 4 ms 1444 KB Output is correct
8 Correct 2 ms 1444 KB Output is correct
9 Correct 14 ms 5780 KB Output is correct
10 Correct 13 ms 5712 KB Output is correct
11 Correct 14 ms 5720 KB Output is correct
12 Correct 1 ms 640 KB Output is correct
13 Correct 1 ms 648 KB Output is correct
14 Correct 0 ms 524 KB Output is correct
15 Correct 0 ms 520 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 4312 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 4264 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -