oj.uz

Submission #540732

# Submission time Handle Problem Language Result Execution time Memory
540732 2022-03-21T15:08:10 Z RyoPham Amusement Park (JOI17_amusement_park) C++14
100 / 100
 164 ms 64120 KB 
#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;

const int lgX = 60;

#define sz(x) (int)x.size()

namespace {
    vector<int> lab;

    set<int> vertices, leaves, T[10005];
    vector<int> num;

    vector<vector<int>> gr;
    vector<bool> vis, ok, in_queue;

    set<int> adj[10005];

    int Find_set(int u) {
        return lab[u] < 0 ? u : lab[u] = Find_set(lab[u]);
    }

    bool Union_sets(int u, int v) {
        u = Find_set(u); v = Find_set(v);
        if(u == v) return false;
        if(lab[u] < lab[v]) swap(u, v);
        lab[v] += lab[u];
        lab[u] = v;
        return true;
    }

    void Dfs(int u) {
        num[u] = sz(vertices);
        vertices.insert(u);
        vis[u] = true;
        for(auto&v: gr[u]) {
            if(vis[v] || sz(vertices) == lgX) continue;
            adj[u].insert(v);
            adj[v].insert(u);
            Dfs(v);
        }
        if(sz(adj[u]) == 1) {
            leaves.insert(u);
        }
    }

    void Expand(int u) {
        if(u == 0) {
            for(auto&v: vertices) {
                T[v] = vertices;
                ok[v] = true;
            }
        }
        else {
            T[u] = vertices;
            ok[u] = true;
        }
        vector<int> cur;
        for(auto&u: vertices) {
            if(in_queue[u]) continue;
            in_queue[u] = true;
            cur.push_back(u);
        }
        for(auto&u: cur) {
            for(auto&v: gr[u]) {
                if(ok[v]) continue;
                auto ptr = leaves.begin();
                if(*ptr == u) ++ptr;
                int w = *ptr;

                assert(sz(adj[w]) == 1);
                if(sz(adj[u]) == 1) leaves.erase(u);
                adj[u].insert(v); adj[v].insert(u);
                int t = *adj[w].begin();
                adj[w].erase(t);
                adj[t].erase(w);
                if(sz(adj[t]) == 1) leaves.insert(t);
                leaves.insert(v); leaves.erase(w);

                vertices.erase(w); vertices.insert(v);

                num[v] = num[w];

                Expand(v);

                if(sz(adj[t]) == 1) leaves.erase(t);
                adj[w].insert(t); adj[t].insert(w);
                adj[v].erase(u); adj[u].erase(v);

                leaves.insert(w); leaves.erase(v);
                if(sz(adj[u]) == 1) leaves.insert(u);
                vertices.erase(v); vertices.insert(w);

            }
        }
    }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    lab.assign(N, -1);
    gr.assign(N, vector<int>());
    for(int i = 0; i < M; ++i) {
        if(Union_sets(A[i], B[i])) {
            gr[A[i]].push_back(B[i]);
            gr[B[i]].push_back(A[i]);
        }
    }

    for(int u = 0; u < N; ++u) {
        assert(!Union_sets(u, 0));
    }

    num.assign(N, -1);
    vis.assign(N, false);
    Dfs(0);

    ok.assign(N, false);
    in_queue.assign(N, false);

    Expand(0);

    for(int u = 0; u < N; ++u) {
        assert(num[u] != -1);
        MessageBoard(u, (X >> num[u]) & 1LL);
    }
}

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

using namespace std;

const int lgX = 60;

#define sz(x) (int)x.size()

vector<int> lab;

set<int> vertices, leaves, T[10005];
vector<int> num;

vector<vector<int>> gr;
vector<bool> vis, ok, in_queue;

set<int> adj[10005];

int find_set(int u) {
    return lab[u] < 0 ? u : lab[u] = find_set(lab[u]);
}

bool union_sets(int u, int v) {
    u = find_set(u); v = find_set(v);
    if(u == v) return false;
    if(lab[u] < lab[v]) swap(u, v);
    lab[v] += lab[u];
    lab[u] = v;
    return true;
}

void dfs(int u) {
    num[u] = sz(vertices);
    vertices.insert(u);
    vis[u] = true;
    for(auto&v: gr[u]) {
        if(vis[v] || sz(vertices) == lgX) continue;
        adj[u].insert(v);
        adj[v].insert(u);
        dfs(v);
    }
    if(sz(adj[u]) == 1) {
        leaves.insert(u);
    }
}

void expand(int u) {
    if(u == 0) {
        for(auto&v: vertices) {
            T[v] = vertices;
            ok[v] = true;
        }
    }
    else {
        T[u] = vertices;
        ok[u] = true;
    }
    vector<int> cur;
    for(auto&u: vertices) {
        if(in_queue[u]) continue;
        in_queue[u] = true;
        cur.push_back(u);
    }
    for(auto&u: cur) {
        for(auto&v: gr[u]) {
            if(ok[v]) continue;
            auto ptr = leaves.begin();
            if(*ptr == u) ++ptr;
            int w = *ptr;

            assert(sz(adj[w]) == 1);
            if(sz(adj[u]) == 1) leaves.erase(u);
            adj[u].insert(v); adj[v].insert(u);
            int t = *adj[w].begin();
            adj[w].erase(t);
            adj[t].erase(w);
            if(sz(adj[t]) == 1) leaves.insert(t);
            leaves.insert(v); leaves.erase(w);

            vertices.erase(w); vertices.insert(v);

            num[v] = num[w];

            expand(v);

            if(sz(adj[t]) == 1) leaves.erase(t);
            adj[w].insert(t); adj[t].insert(w);
            adj[v].erase(u); adj[u].erase(v);

            leaves.insert(w); leaves.erase(v);
            if(sz(adj[u]) == 1) leaves.insert(u);
            vertices.erase(v); vertices.insert(w);

        }
    }
}

int bit[lgX], cnt_move = 0;

void dfs2(int u, int par, const int&r) {
    for(auto&v: gr[u]) {
        if(T[r].count(v) && v != par) {
            bit[num[v]] = Move(v);
            dfs2(v, u, r);
        }
    }
    if(par != -1) {
        Move(par);
    }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int subtask) {
    lab.assign(N, -1);
    gr.assign(N, vector<int>());
    for(int i = 0; i < M; ++i) {
        if(union_sets(A[i], B[i])) {
            gr[A[i]].push_back(B[i]);
            gr[B[i]].push_back(A[i]);
        }
    }

    num.assign(N, -1);
    vis.assign(N, false);
    dfs(0);

    ok.assign(N, false);
    in_queue.assign(N, false);

    expand(0);

    assert(sz(T[P]) == lgX);

    fill(begin(bit), end(bit), -1);

    bit[num[P]] = V;
    dfs2(P, -1, P);

    long long ans = 0;

    for(int i = 0; i < lgX; ++i) {
        //assert(bit[i] != -1);
        if(bit[i]) ans ^= (1LL << i);
    }

    return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2828 KB Output is correct
2 Correct 3 ms 3352 KB Output is correct
3 Correct 5 ms 4360 KB Output is correct
4 Correct 2 ms 3088 KB Output is correct
5 Correct 4 ms 3072 KB Output is correct
6 Correct 4 ms 3596 KB Output is correct
7 Correct 5 ms 4368 KB Output is correct
8 Correct 4 ms 4104 KB Output is correct
9 Correct 4 ms 4116 KB Output is correct
10 Correct 3 ms 3336 KB Output is correct
11 Correct 5 ms 3672 KB Output is correct
12 Correct 2 ms 2840 KB Output is correct
13 Correct 4 ms 4364 KB Output is correct
14 Correct 6 ms 4364 KB Output is correct
15 Correct 6 ms 4340 KB Output is correct
16 Correct 6 ms 4244 KB Output is correct
17 Correct 5 ms 4236 KB Output is correct
18 Correct 5 ms 4240 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 61864 KB Output is correct
2 Correct 149 ms 62008 KB Output is correct
3 Correct 133 ms 61880 KB Output is correct
4 Correct 123 ms 60904 KB Output is correct
5 Correct 133 ms 62736 KB Output is correct
6 Correct 124 ms 62208 KB Output is correct
7 Correct 128 ms 62160 KB Output is correct
8 Correct 125 ms 62432 KB Output is correct
9 Correct 128 ms 62496 KB Output is correct
10 Correct 113 ms 61108 KB Output is correct
11 Correct 119 ms 61240 KB Output is correct
12 Correct 108 ms 55740 KB Output is correct
13 Correct 108 ms 55820 KB Output is correct
14 Correct 114 ms 58360 KB Output is correct
15 Correct 122 ms 60872 KB Output is correct
16 Correct 124 ms 60868 KB Output is correct
17 Correct 122 ms 60988 KB Output is correct
18 Correct 127 ms 61088 KB Output is correct
19 Correct 131 ms 60944 KB Output is correct
20 Correct 119 ms 62848 KB Output is correct
21 Correct 112 ms 61976 KB Output is correct
22 Correct 126 ms 61972 KB Output is correct
23 Correct 124 ms 62464 KB Output is correct
24 Correct 164 ms 62196 KB Output is correct
25 Correct 126 ms 62332 KB Output is correct
26 Correct 127 ms 62468 KB Output is correct
27 Correct 134 ms 62408 KB Output is correct
28 Correct 129 ms 62664 KB Output is correct
29 Correct 118 ms 57008 KB Output is correct
30 Correct 139 ms 59480 KB Output is correct
31 Correct 4 ms 3340 KB Output is correct
32 Correct 4 ms 3596 KB Output is correct
33 Correct 5 ms 4168 KB Output is correct
34 Correct 3 ms 3340 KB Output is correct
35 Correct 2 ms 3092 KB Output is correct
36 Correct 3 ms 3092 KB Output is correct
37 Correct 2 ms 2820 KB Output is correct
38 Correct 2 ms 2832 KB Output is correct
39 Correct 2 ms 2820 KB Output is correct
40 Correct 3 ms 3088 KB Output is correct
41 Correct 2 ms 3076 KB Output is correct
42 Correct 3 ms 2808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3080 KB Output is correct
2 Correct 3 ms 3084 KB Output is correct
3 Correct 3 ms 3092 KB Output is correct
4 Correct 23 ms 12448 KB Output is correct
5 Correct 24 ms 12552 KB Output is correct
6 Correct 20 ms 12540 KB Output is correct
7 Correct 19 ms 12472 KB Output is correct
8 Correct 19 ms 12508 KB Output is correct
9 Correct 104 ms 63984 KB Output is correct
10 Correct 122 ms 64112 KB Output is correct
11 Correct 114 ms 63944 KB Output is correct
12 Correct 2 ms 2820 KB Output is correct
13 Correct 3 ms 2948 KB Output is correct
14 Correct 2 ms 2820 KB Output is correct
15 Correct 3 ms 2820 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 61820 KB Output is correct
2 Correct 134 ms 61868 KB Output is correct
3 Correct 134 ms 61784 KB Output is correct
4 Correct 133 ms 60956 KB Output is correct
5 Correct 130 ms 63680 KB Output is correct
6 Correct 127 ms 62544 KB Output is correct
7 Correct 137 ms 62608 KB Output is correct
8 Correct 132 ms 61748 KB Output is correct
9 Correct 125 ms 61940 KB Output is correct
10 Correct 134 ms 61120 KB Output is correct
11 Correct 120 ms 61140 KB Output is correct
12 Correct 111 ms 55744 KB Output is correct
13 Correct 118 ms 55708 KB Output is correct
14 Correct 119 ms 58300 KB Output is correct
15 Correct 122 ms 61008 KB Output is correct
16 Correct 134 ms 60896 KB Output is correct
17 Correct 126 ms 61088 KB Output is correct
18 Correct 123 ms 61136 KB Output is correct
19 Correct 134 ms 61028 KB Output is correct
20 Correct 112 ms 62920 KB Output is correct
21 Correct 106 ms 62120 KB Output is correct
22 Correct 144 ms 62476 KB Output is correct
23 Correct 134 ms 62252 KB Output is correct
24 Correct 134 ms 62232 KB Output is correct
25 Correct 125 ms 62416 KB Output is correct
26 Correct 140 ms 62440 KB Output is correct
27 Correct 130 ms 62656 KB Output is correct
28 Correct 129 ms 62052 KB Output is correct
29 Correct 114 ms 56796 KB Output is correct
30 Correct 119 ms 59356 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 61872 KB Output is correct
2 Correct 127 ms 61828 KB Output is correct
3 Correct 139 ms 61816 KB Output is correct
4 Correct 122 ms 61048 KB Output is correct
5 Correct 126 ms 64120 KB Output is correct
6 Correct 122 ms 62076 KB Output is correct
7 Correct 124 ms 61944 KB Output is correct
8 Correct 124 ms 62540 KB Output is correct
9 Correct 121 ms 62300 KB Output is correct
10 Correct 113 ms 61128 KB Output is correct
11 Correct 110 ms 61128 KB Output is correct
12 Correct 107 ms 55696 KB Output is correct
13 Correct 109 ms 55700 KB Output is correct
14 Correct 117 ms 58320 KB Output is correct
15 Correct 124 ms 60896 KB Output is correct
16 Correct 123 ms 60932 KB Output is correct
17 Correct 130 ms 61020 KB Output is correct
18 Correct 120 ms 61008 KB Output is correct
19 Correct 124 ms 61024 KB Output is correct
20 Correct 103 ms 62920 KB Output is correct
21 Correct 122 ms 62012 KB Output is correct
22 Correct 127 ms 62404 KB Output is correct
23 Correct 123 ms 62316 KB Output is correct
24 Correct 129 ms 62180 KB Output is correct
25 Correct 127 ms 62260 KB Output is correct
26 Correct 128 ms 61920 KB Output is correct
27 Correct 131 ms 62800 KB Output is correct
28 Correct 126 ms 62684 KB Output is correct
29 Correct 115 ms 57320 KB Output is correct
30 Correct 119 ms 59616 KB Output is correct
31 Correct 3 ms 3312 KB Output is correct
32 Correct 4 ms 3596 KB Output is correct
33 Correct 5 ms 4256 KB Output is correct
34 Correct 4 ms 3340 KB Output is correct
35 Correct 4 ms 3096 KB Output is correct
36 Correct 2 ms 3084 KB Output is correct
37 Correct 2 ms 2820 KB Output is correct
38 Correct 2 ms 2820 KB Output is correct
39 Correct 2 ms 2996 KB Output is correct
40 Correct 2 ms 3076 KB Output is correct
41 Correct 2 ms 3080 KB Output is correct
42 Correct 2 ms 2828 KB Output is correct