oj.uz

Submission #540724

# Submission time Handle Problem Language Result Execution time Memory
540724 2022-03-21T14:34:58 Z RyoPham Amusement Park (JOI17_amusement_park) C++14
10 / 100
 101 ms 64208 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_leaves;
        for(auto&u: leaves) {
            if(in_queue[u]) continue;
            in_queue[u] = true;
            cur_leaves.push_back(u);
        }
        for(auto&u: cur_leaves) {
            for(auto&v: gr[u]) {
                if(ok[v]) continue;
                auto ptr = leaves.begin();
                if(*ptr == u) ++ptr;
                int w = *ptr;
                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.erase(u); 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[t].insert(w);
                adj[w].insert(t);
                adj[v].erase(u); adj[u].erase(v);

                leaves.insert(w); leaves.erase(v); 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]);
        }
    }

    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_leaves;
    for(auto&u: leaves) {
        if(in_queue[u]) continue;
        in_queue[u] = true;
        cur_leaves.push_back(u);
    }
    for(auto&u: cur_leaves) {
        for(auto&v: gr[u]) {
            if(ok[v]) continue;
            auto ptr = leaves.begin();
            if(*ptr == u) ++ptr;
            int w = *ptr;
            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.erase(u); 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[t].insert(w);
            adj[w].insert(t);
            adj[v].erase(u); adj[u].erase(v);

            leaves.insert(w); leaves.erase(v); 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);

    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;
}

Compilation message

Joi.cpp: In function 'void {anonymous}::Expand(int)':
Joi.cpp:82:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   82 |                 if(sz(adj[t]) == 1) leaves.erase(t); adj[t].insert(w);
      |                 ^~
Joi.cpp:82:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   82 |                 if(sz(adj[t]) == 1) leaves.erase(t); adj[t].insert(w);
      |                                                      ^~~

Ioi.cpp: In function 'void expand(int)':
Ioi.cpp:81:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   81 |             if(sz(adj[t]) == 1) leaves.erase(t); adj[t].insert(w);
      |             ^~
Ioi.cpp:81:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   81 |             if(sz(adj[t]) == 1) leaves.erase(t); adj[t].insert(w);
      |                                                  ^~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3076 KB Output is correct
2 Correct 2 ms 3104 KB Output is correct
3 Correct 2 ms 3080 KB Output is correct
4 Correct 16 ms 12464 KB Output is correct
5 Correct 17 ms 12504 KB Output is correct
6 Correct 18 ms 12476 KB Output is correct
7 Correct 19 ms 12488 KB Output is correct
8 Correct 17 ms 12612 KB Output is correct
9 Correct 101 ms 64208 KB Output is correct
10 Correct 96 ms 63944 KB Output is correct
11 Correct 98 ms 63976 KB Output is correct
12 Correct 2 ms 2820 KB Output is correct
13 Correct 2 ms 3076 KB Output is correct
14 Correct 2 ms 2820 KB Output is correct
15 Correct 2 ms 2820 KB Output is correct

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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