oj.uz

Submission #32435

# Submission time Handle Problem Language Result Execution time Memory
32435 2017-10-10T11:56:13 Z aome Amusement Park (JOI17_amusement_park) C++14
0 / 100
 41 ms 7496 KB 
#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();
        }
        assert(go[i].size() == 0);
        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;
        }
    }
    for (int i = 0; i < n; ++i) {
        MessageBoard(i, color[i]);
    }
}

#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;
        visit[v] = 1, res += (1LL << pos[v]) * Move(v), 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();
        }
        assert(go[i].size() == 0);
        go[i] = tmp;
        for (int j = 0; j < 60; ++j) {
            if (have[j] != -1) visit[have[j]] = 0;
        }
    }
    memset(visit, 0, sizeof visit);
    for (int i = 0; i < 60; ++i) {
        ok[go[in[p]][i]] = 1;
    }
    res += (1LL << pos[p]) * v, visit[p] = 1, solve(p);
    return res;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5912 KB Output is correct
2 Correct 0 ms 5912 KB Output is correct
3 Incorrect 0 ms 5912 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7496 KB Output is correct
2 Correct 41 ms 7496 KB Output is correct
3 Correct 32 ms 7496 KB Output is correct
4 Correct 19 ms 6968 KB Output is correct
5 Correct 18 ms 6704 KB Output is correct
6 Incorrect 19 ms 7232 KB Wrong Answer [7]
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5912 KB Output is correct
2 Correct 0 ms 5912 KB Output is correct
3 Incorrect 0 ms 5912 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7496 KB Output is correct
2 Incorrect 41 ms 7496 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7496 KB Output is correct
2 Correct 39 ms 7496 KB Output is correct
3 Correct 38 ms 7496 KB Output is correct
4 Correct 22 ms 6968 KB Output is correct
5 Incorrect 22 ms 6968 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -