Submission #1174198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174198		nhphuc	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	139 ms	4936 KiB

Joi

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

using namespace std;

const int N = 10007;

int par[N], mess[N], leaf;
bool ing[N];
vector<int> g[N], adj[N], group[N];

void bfs (int n, int src){
    fill(par, par + n, -1);
    queue<int> q;
    vector<int> d(n, -1);
    d[src] = 0;
    q.push(src);
    while (q.size()){
        int u = q.front(); q.pop();
        for (int v : g[u]){
            if (d[v] == -1){
                par[v] = u;
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    return;
}

void init (int n){
    fill(mess, mess + n, -1);
    for (int i = 0; i < n; ++i){
        g[i].clear();
        adj[i].clear();
    }
}

void dfs (int u, int p = -1){
    int child = 0;
    for (int v : adj[u]){
        if (v != p && ing[v]){
            ++child;
            dfs(v, u);
        }
    }
    if (child == 0){
        leaf = u;
    }
    return;
}

void Joi (int n, int m, int a[], int b[], long long x, int subtask){
    init(n);
    for (int i = 0; i < m; ++i){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    bfs(n, 0);
    for (int i = 0; i < n; ++i){
        if (par[i] != -1){
            adj[i].push_back(par[i]);
            adj[par[i]].push_back(i);
        }
    }
    vector<int> st;
    {
        queue<int> q;
        q.push(0);
        while (st.size() < 60 && q.size()){
            int u = q.front(); q.pop();
            mess[u] = st.size();
            st.push_back(u);
            for (int v : adj[u]){
                if (mess[v] == -1){
                    q.push(v);
                }
            }
        }
    }
    queue<int> q;
    for (int u : st){
        group[u] = st;
        q.push(u);
    }
    while (q.size()){
        int u = q.front(); q.pop();
        for (int v : adj[u]){
            if (mess[v] == -1){
                for (int uu : group[u]){
                    ing[uu] = true;
                }
                dfs(u);
                group[v] = group[u];
                for (int i = 0; i < group[v].size(); ++i){
                    if (group[v][i] == leaf){
                        group[v][i] = v;
                    }
                }
                mess[v] = mess[leaf];
                for (int uu : group[u]){
                    ing[uu] = false;
                }
                q.push(v);
            }
        }
    }
    for (int i = 0; i < n; ++i){
        MessageBoard(i, (x >> mess[i] & 1));
    }
    return;
}

Ioi

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

using namespace std;

const int N = 10007;

int par[N], mess[N], leaf;
bool ing[N];
vector<int> g[N], adj[N], group[N];

void bfs (int n, int src){
    fill(par, par + n, -1);
    queue<int> q;
    vector<int> d(n, -1);
    d[src] = 0;
    q.push(src);
    while (q.size()){
        int u = q.front(); q.pop();
        for (int v : g[u]){
            if (d[v] == -1){
                par[v] = u;
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    return;
}

void init (int n){
    fill(mess, mess + n, -1);
    for (int i = 0; i < n; ++i){
        g[i].clear();
        adj[i].clear();
    }
}

void dfs (int u, int p = -1){
    int child = 0;
    for (int v : adj[u]){
        if (v != p && ing[v]){
            ++child;
            dfs(v, u);
        }
    }
    if (child == 0){
        leaf = u;
    }
    return;
}

void dfs2 (int u, long long &answer, int p = -1){
    for (int v : adj[u]){
        if (ing[v] && v != p){
            answer += (1ll << mess[v]) * Move(v);
            dfs2(v, answer, u);
        }
    }
    if (p != -1){
        int f = Move(p);
    }
    return;
}

long long Ioi (int n, int m, int a[], int b[], int p, int v, int subtask){
    init(n);
    for (int i = 0; i < m; ++i){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    bfs(n, 0);
    for (int i = 0; i < n; ++i){
        if (par[i] != -1){
            adj[i].push_back(par[i]);
            adj[par[i]].push_back(i);
        }
    }
    vector<int> st;
    {
        queue<int> q;
        q.push(0);
        while (st.size() < 60 && q.size()){
            int u = q.front(); q.pop();
            mess[u] = st.size();
            st.push_back(u);
            for (int v : adj[u]){
                if (mess[v] == -1){
                    q.push(v);
                }
            }
        }
    }
    queue<int> q;
    for (int u : st){
        group[u] = st;
        q.push(u);
    }
    while (q.size()){
        int u = q.front(); q.pop();
        for (int v : adj[u]){
            if (mess[v] == -1){
                for (int uu : group[u]){
                    ing[uu] = true;
                }
                dfs(u);
                group[v] = group[u];
                for (int i = 0; i < group[v].size(); ++i){
                    if (group[v][i] == leaf){
                        group[v][i] = v;
                    }
                }
                mess[v] = mess[leaf];
                for (int uu : group[u]){
                    ing[uu] = false;
                }
                q.push(v);
            }
        }
    }
    long long answer = (1ll << mess[p]) * v;
    for (int uu : group[p]){
        ing[uu] = true;
    }
    dfs2(p, answer);
    return answer;
}

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