Submission #32452

#	Time	Username	Problem	Language	Result	Execution time	Memory
32452		aome	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	65 ms	11052 KiB

Joi

#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;

const int N = 10005;

static int num;
static int in[N], pos[N];
static int color[N];
static int have[60];
static bool visit[N];
static vector<int> G[N];
static vector<int> go[N];

static void dfs(int u) {
    in[u] = num, pos[u] = go[num].size(), go[num].push_back(u);
    for (auto v : G[u]) {
        if (go[num].size() == 60) return;
        if (in[v]) continue; dfs(v);
    }
}

static void redfs(int u, int x, int &need) {
    visit[u] = 1;
    for (auto v : G[u]) {
        if (!need) return;
        if (visit[v]) continue;
        if (in[v] != x) have[pos[v]] = v, need--;
        redfs(v, x, need);
    }
}

void Joi(int n, int m, int a[], int b[], long long x, int t) {
    for (int i = 0; i < m; ++i) {
        G[a[i]].push_back(b[i]), G[b[i]].push_back(a[i]);
    }
    for (int i = 0; i < n; ++i) {
        if (in[i]) continue;
        ++num, dfs(i);
    }
    memset(color, -1, sizeof color);
    for (int i = 1; i <= num; ++i) {
        if (go[i].size() != 60) continue;
        for (int j = 0; j < 60; ++j) {
            color[go[i][j]] = x >> j & 1;
        }
        for (int j = 0; j < 60; ++j) {
            vector<int> tmp;
            int u = go[i][j];
            for (auto v : G[u]) {
                if (in[u] == in[v]) tmp.push_back(v);
            }
            G[u] = tmp;
        }
    }
    for (int i = 1; i <= num; ++i) {
        if (go[i].size() == 60) continue;
        memset(have, -1, sizeof have);
        int need = 60 - go[i].size();
        redfs(go[i][0], i, need);
        vector<int> tmp;
        for (int j = 0; j < 60; ++j) {
            if (have[j] != -1) {
                tmp.push_back(have[j]); continue;
            }
            tmp.push_back(go[i].back()), go[i].pop_back();
        }
        go[i] = tmp;
        for (int j = 0; j < 60; ++j) {
            color[go[i][j]] = x >> j & 1;
            if (have[j] != -1) visit[have[j]] = 0;
        }
    }
    //cout << "Ioi\n";
    //for (auto i : go[in[4]]) cout << i << ' ' << color[i] << '\n';
    for (int i = 0; i < n; ++i) {
        MessageBoard(i, color[i]);
    }
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 10005;

static int num;
static int in[N], pos[N];
static int have[60];
long long res;
static bool visit[N];
bool ok[N];
static vector<int> G[N];
static vector<int> go[N];

static void dfs(int u) {
    in[u] = num, pos[u] = go[num].size(), go[num].push_back(u);
    for (auto v : G[u]) {
        if (go[num].size() == 60) return;
        if (in[v]) continue; dfs(v);
    }
}

static void redfs(int u, int x, int &need) {
    visit[u] = 1;
    for (auto v : G[u]) {
        if (!need) return;
        if (visit[v]) continue;
        if (in[v] != x) {
            have[pos[v]] = v, need--;
        }
        redfs(v, x, need);
    }
}

void solve(int u) {
    for (auto v : G[u]) {
        if (!ok[v] || visit[v]) continue;
        bool t = Move(v);
        //cout << v << ' ' << t << '\n';
        visit[v] = 1, res += (1LL << pos[v]) * t, solve(v), Move(u);
    }
}

long long Ioi(int n, int m, int a[], int b[], int p, int v, int t) {
    for (int i = 0; i < m; ++i) {
        G[a[i]].push_back(b[i]), G[b[i]].push_back(a[i]);
    }
    for (int i = 0; i < n; ++i) {
        if (in[i]) continue;
        ++num, dfs(i);
    }
    for (int i = 1; i <= num; ++i) {
        if (go[i].size() != 60) continue;
        for (int j = 0; j < 60; ++j) {
            vector<int> tmp;
            int u = go[i][j];
            for (auto v : G[u]) {
                if (in[u] == in[v]) tmp.push_back(v);
            }
            G[u] = tmp;
        }
    }
    for (int i = 1; i <= num; ++i) {
        if (go[i].size() == 60) continue;
        memset(have, -1, sizeof have);
        int need = 60 - go[i].size();
        redfs(go[i][0], i, need);
        vector<int> tmp;
        for (int j = 0; j < 60; ++j) {
            if (have[j] != -1) {
                tmp.push_back(have[j]); continue;
            }
            tmp.push_back(go[i].back()), go[i].pop_back();
        }
        go[i] = tmp;
        for (int j = 0; j < 60; ++j) {
            if (have[j] != -1) visit[have[j]] = 0;
            pos[go[i][j]] = j;
        }
    }
    memset(visit, 0, sizeof visit);
    for (int i = 0; i < 60; ++i) {
        ok[go[in[p]][i]] = 1;
    }
    //cout << "Ioi\n";
    res += (1LL << pos[p]) * v, visit[p] = 1, solve(p);
    //cout << res << '\n';
    return res;
}

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