답안 #32452 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32452	2017-10-10T13:08:35 Z	aome	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	65 ms	11052 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();
        }
        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]);
    }
}

#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.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	5908 KB	Output is correct
2	Correct	0 ms	5908 KB	Output is correct
3	Correct	0 ms	5908 KB	Output is correct
4	Correct	0 ms	5908 KB	Output is correct
5	Correct	0 ms	5908 KB	Output is correct
6	Correct	0 ms	5908 KB	Output is correct
7	Correct	0 ms	5908 KB	Output is correct
8	Correct	0 ms	6172 KB	Output is correct
9	Correct	0 ms	5908 KB	Output is correct
10	Correct	0 ms	5908 KB	Output is correct
11	Correct	3 ms	6172 KB	Output is correct
12	Correct	0 ms	5908 KB	Output is correct
13	Correct	0 ms	5908 KB	Output is correct
14	Correct	0 ms	5908 KB	Output is correct
15	Correct	0 ms	5908 KB	Output is correct
16	Correct	0 ms	5908 KB	Output is correct
17	Correct	0 ms	5908 KB	Output is correct
18	Correct	0 ms	5908 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	7492 KB	Output is correct
2	Correct	39 ms	7492 KB	Output is correct
3	Correct	49 ms	7492 KB	Output is correct
4	Correct	18 ms	6964 KB	Output is correct
5	Correct	19 ms	6700 KB	Output is correct
6	Correct	27 ms	7228 KB	Output is correct
7	Correct	22 ms	7228 KB	Output is correct
8	Correct	25 ms	7228 KB	Output is correct
9	Correct	28 ms	7228 KB	Output is correct
10	Correct	46 ms	11052 KB	Output is correct
11	Correct	65 ms	11044 KB	Output is correct
12	Correct	22 ms	6700 KB	Output is correct
13	Correct	15 ms	6700 KB	Output is correct
14	Correct	22 ms	6700 KB	Output is correct
15	Correct	22 ms	6964 KB	Output is correct
16	Correct	18 ms	6964 KB	Output is correct
17	Correct	18 ms	6964 KB	Output is correct
18	Correct	22 ms	6964 KB	Output is correct
19	Correct	22 ms	6964 KB	Output is correct
20	Correct	9 ms	6700 KB	Output is correct
21	Correct	6 ms	6700 KB	Output is correct
22	Correct	26 ms	7492 KB	Output is correct
23	Correct	35 ms	7492 KB	Output is correct
24	Correct	35 ms	7492 KB	Output is correct
25	Correct	32 ms	7492 KB	Output is correct
26	Correct	27 ms	7492 KB	Output is correct
27	Correct	28 ms	7492 KB	Output is correct
28	Correct	32 ms	7492 KB	Output is correct
29	Correct	19 ms	7492 KB	Output is correct
30	Correct	27 ms	7492 KB	Output is correct
31	Correct	0 ms	5908 KB	Output is correct
32	Correct	0 ms	5908 KB	Output is correct
33	Correct	0 ms	6172 KB	Output is correct
34	Correct	0 ms	5908 KB	Output is correct
35	Correct	0 ms	5908 KB	Output is correct
36	Correct	0 ms	5908 KB	Output is correct
37	Correct	0 ms	5908 KB	Output is correct
38	Correct	0 ms	5908 KB	Output is correct
39	Correct	0 ms	5908 KB	Output is correct
40	Correct	0 ms	5908 KB	Output is correct
41	Correct	0 ms	5908 KB	Output is correct
42	Correct	0 ms	5908 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	5908 KB	Output is correct
2	Correct	0 ms	5908 KB	Output is correct
3	Correct	0 ms	5908 KB	Output is correct
4	Correct	0 ms	6172 KB	Output is correct
5	Correct	0 ms	6172 KB	Output is correct
6	Correct	0 ms	6172 KB	Output is correct
7	Correct	0 ms	6172 KB	Output is correct
8	Correct	0 ms	6172 KB	Output is correct
9	Correct	12 ms	6700 KB	Output is correct
10	Correct	12 ms	6700 KB	Output is correct
11	Correct	9 ms	6700 KB	Output is correct
12	Correct	0 ms	5908 KB	Output is correct
13	Correct	0 ms	5908 KB	Output is correct
14	Correct	0 ms	5908 KB	Output is correct
15	Correct	0 ms	5908 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	7492 KB	Output is correct
2	Correct	41 ms	7492 KB	Output is correct
3	Correct	52 ms	7492 KB	Output is correct
4	Correct	22 ms	6964 KB	Output is correct
5	Correct	35 ms	6700 KB	Output is correct
6	Correct	28 ms	7228 KB	Output is correct
7	Correct	32 ms	7228 KB	Output is correct
8	Correct	28 ms	7228 KB	Output is correct
9	Correct	22 ms	7228 KB	Output is correct
10	Correct	49 ms	11052 KB	Output is correct
11	Correct	48 ms	11052 KB	Output is correct
12	Correct	18 ms	6700 KB	Output is correct
13	Correct	18 ms	6700 KB	Output is correct
14	Correct	15 ms	6700 KB	Output is correct
15	Correct	15 ms	6964 KB	Output is correct
16	Correct	15 ms	6964 KB	Output is correct
17	Correct	18 ms	6964 KB	Output is correct
18	Correct	22 ms	6964 KB	Output is correct
19	Correct	19 ms	6964 KB	Output is correct
20	Correct	9 ms	6700 KB	Output is correct
21	Correct	26 ms	6700 KB	Output is correct
22	Correct	28 ms	7492 KB	Output is correct
23	Correct	32 ms	7492 KB	Output is correct
24	Correct	35 ms	7492 KB	Output is correct
25	Correct	28 ms	7492 KB	Output is correct
26	Correct	32 ms	7492 KB	Output is correct
27	Correct	39 ms	7492 KB	Output is correct
28	Correct	41 ms	7492 KB	Output is correct
29	Correct	25 ms	7492 KB	Output is correct
30	Correct	35 ms	7492 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	7492 KB	Output is correct
2	Correct	45 ms	7492 KB	Output is correct
3	Correct	41 ms	7492 KB	Output is correct
4	Correct	27 ms	6964 KB	Output is correct
5	Correct	19 ms	6964 KB	Output is correct
6	Correct	22 ms	7228 KB	Output is correct
7	Correct	26 ms	7228 KB	Output is correct
8	Correct	26 ms	7228 KB	Output is correct
9	Correct	36 ms	7228 KB	Output is correct
10	Correct	52 ms	11052 KB	Output is correct
11	Correct	46 ms	11052 KB	Output is correct
12	Correct	18 ms	6700 KB	Output is correct
13	Correct	18 ms	6700 KB	Output is correct
14	Correct	18 ms	6700 KB	Output is correct
15	Correct	22 ms	6964 KB	Output is correct
16	Correct	27 ms	6964 KB	Output is correct
17	Correct	19 ms	6964 KB	Output is correct
18	Correct	22 ms	6964 KB	Output is correct
19	Correct	26 ms	6964 KB	Output is correct
20	Correct	15 ms	6700 KB	Output is correct
21	Correct	15 ms	6700 KB	Output is correct
22	Correct	32 ms	7492 KB	Output is correct
23	Correct	32 ms	7492 KB	Output is correct
24	Correct	32 ms	7492 KB	Output is correct
25	Correct	35 ms	7492 KB	Output is correct
26	Correct	27 ms	7492 KB	Output is correct
27	Correct	35 ms	7492 KB	Output is correct
28	Correct	32 ms	7492 KB	Output is correct
29	Correct	28 ms	7492 KB	Output is correct
30	Correct	28 ms	7492 KB	Output is correct
31	Correct	0 ms	5908 KB	Output is correct
32	Correct	0 ms	5908 KB	Output is correct
33	Correct	0 ms	6172 KB	Output is correct
34	Correct	0 ms	5908 KB	Output is correct
35	Correct	0 ms	5908 KB	Output is correct
36	Correct	0 ms	5908 KB	Output is correct
37	Correct	0 ms	5908 KB	Output is correct
38	Correct	0 ms	5908 KB	Output is correct
39	Correct	0 ms	5908 KB	Output is correct
40	Correct	0 ms	5908 KB	Output is correct
41	Correct	0 ms	5908 KB	Output is correct
42	Correct	0 ms	5908 KB	Output is correct

답안 #32452

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 55.0 / 55.0

Subtask #5 17.0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
55.0 / 55.0

Subtask #5
17.0 / 17.0