답안 #137034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137034	2019-07-26T23:30:41 Z	osaaateiasavtnl	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	35 ms	5676 KB

#include<bits/stdc++.h>
#include"Joi.h"
using namespace std;
#define color MessageBoard
#define app push_back
const int N = 20001;
vector <int> g[N];
int tin[N], ptr = 0;
bool used[N];
void dfs(int u, long long x) {
    used[u] = 1;
    tin[u] = ptr++;
    int b = tin[u] % 60;
    color(u, (x >> b) & 1);
    for (int v : g[u]) {
        if (!used[v]) {
            dfs(v, x);
        }   
    }   
}   
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]].app(b[i]);
        g[b[i]].app(a[i]);    
    }   
    dfs(0, x);
}

#include<bits/stdc++.h>
#include"Ioi.h"
#define move Move
#define app push_back
using namespace std;
const int N = 20001;
vector <int> g[N];
int tin[N], cnt[N], par[N], ptr = 0;
bool used[N];
vector <int> tree[N];
void dfs(int u) {
    used[u] = 1; cnt[u] = 1; tin[u] = ptr++;
    for (int v : g[u]) {
        if (!used[v]) {
            dfs(v);
            par[v] = u; tree[u].app(v); cnt[u] += cnt[v];
        }   
    }   
}   
int vis = 0;
bool want[N];
int vert[60];
int ans[N];
int h[N];
void dfs1(int u, int p) {
    if (vis == 60) return;
    ++vis;              
    int b = tin[u] % 60;
    want[u] = vert[b] == -1;
    h[u] = 0;
    for (int v : tree[u]) {
        dfs1(v, u);
        want[u] |= want[v];
        h[u] = max(h[u], h[v] + 1);
    }   
}   
void dfs2(int u, int p, bool r) {
    if (tree[u].empty()) return;
    int mx = -1;
    for (int v : tree[u]) {
        if (want[v]) {
            if (mx == -1 || h[mx] < h[v]) mx = v;
        }
    }   
    if (r && mx != -1) {
        for (int v : tree[u]) {
            if (want[v] && v != mx) {
                vert[tin[v] % 60] = v;
                ans[v] = move(v);
                dfs2(v, u, 0);
                move(u);
            }
        }
        vert[tin[mx] % 60] = mx;
        ans[mx] = move(mx);
        dfs2(mx, u, 1);
    }
    else {
        for (int v : tree[u]) {
            if (want[v]) {
                vert[tin[v] % 60] = v;
                ans[v] = move(v);
                dfs2(v, u, 0);
                move(u);
            }
        }
    }   
}   
long long Ioi(int n, int m, int a[], int b[], int u, int v, int t) {
    for (int i = 0; i < 60; ++i) vert[i] = -1;
    for (int i = 0; i < m; ++i) {
        g[a[i]].app(b[i]);
        g[b[i]].app(a[i]);
    }   
    dfs(0);
    ans[u] = v;
    vert[tin[u] % 60] = u;
    while (cnt[u] < 60) {
        u = par[u];
        ans[u] = move(u);
        vert[tin[u] % 60] = u;
    }   
    dfs1(u, par[u]);
    if (want[u]) dfs2(u, par[u], 1);
    long long x = 0;
    for (int i = 0; i < 60; ++i) {
        x += (1ll << i) * ans[vert[i]];
    }   
    return x;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2420 KB	Output is correct
2	Correct	5 ms	2288 KB	Output is correct
3	Correct	6 ms	2432 KB	Output is correct
4	Correct	5 ms	2424 KB	Output is correct
5	Correct	6 ms	2296 KB	Output is correct
6	Correct	5 ms	2160 KB	Output is correct
7	Correct	6 ms	2408 KB	Output is correct
8	Correct	5 ms	2432 KB	Output is correct
9	Correct	5 ms	2172 KB	Output is correct
10	Correct	5 ms	2416 KB	Output is correct
11	Correct	9 ms	2604 KB	Output is correct
12	Correct	5 ms	2160 KB	Output is correct
13	Correct	5 ms	2168 KB	Output is correct
14	Correct	5 ms	2276 KB	Output is correct
15	Correct	6 ms	2536 KB	Output is correct
16	Correct	5 ms	2432 KB	Output is correct
17	Correct	5 ms	2432 KB	Output is correct
18	Correct	5 ms	2168 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	5448 KB	Output is correct
2	Correct	33 ms	5676 KB	Output is correct
3	Correct	33 ms	5648 KB	Output is correct
4	Correct	20 ms	4412 KB	Output is correct
5	Correct	24 ms	4760 KB	Output is correct
6	Correct	22 ms	4592 KB	Output is correct
7	Correct	22 ms	4460 KB	Output is correct
8	Correct	20 ms	4408 KB	Output is correct
9	Correct	22 ms	4560 KB	Output is correct
10	Correct	18 ms	4228 KB	Output is correct
11	Correct	20 ms	4032 KB	Output is correct
12	Correct	20 ms	4092 KB	Output is correct
13	Correct	20 ms	4116 KB	Output is correct
14	Correct	22 ms	4068 KB	Output is correct
15	Correct	20 ms	4160 KB	Output is correct
16	Correct	20 ms	4176 KB	Output is correct
17	Correct	20 ms	4188 KB	Output is correct
18	Correct	22 ms	4160 KB	Output is correct
19	Correct	20 ms	4032 KB	Output is correct
20	Correct	18 ms	4792 KB	Output is correct
21	Correct	18 ms	4748 KB	Output is correct
22	Correct	22 ms	4640 KB	Output is correct
23	Correct	24 ms	4760 KB	Output is correct
24	Correct	23 ms	4640 KB	Output is correct
25	Correct	22 ms	4640 KB	Output is correct
26	Correct	23 ms	4844 KB	Output is correct
27	Correct	24 ms	4728 KB	Output is correct
28	Correct	23 ms	4768 KB	Output is correct
29	Correct	20 ms	4468 KB	Output is correct
30	Correct	20 ms	4492 KB	Output is correct
31	Correct	5 ms	2300 KB	Output is correct
32	Correct	6 ms	2428 KB	Output is correct
33	Correct	6 ms	2440 KB	Output is correct
34	Correct	5 ms	2300 KB	Output is correct
35	Correct	6 ms	2300 KB	Output is correct
36	Correct	5 ms	2544 KB	Output is correct
37	Correct	5 ms	2420 KB	Output is correct
38	Correct	5 ms	2412 KB	Output is correct
39	Correct	7 ms	2392 KB	Output is correct
40	Correct	5 ms	2196 KB	Output is correct
41	Correct	5 ms	2164 KB	Output is correct
42	Correct	5 ms	2184 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2296 KB	Output is correct
2	Correct	5 ms	2416 KB	Output is correct
3	Correct	5 ms	2296 KB	Output is correct
4	Correct	7 ms	2792 KB	Output is correct
5	Correct	8 ms	2788 KB	Output is correct
6	Correct	9 ms	2824 KB	Output is correct
7	Correct	8 ms	2844 KB	Output is correct
8	Correct	8 ms	2920 KB	Output is correct
9	Correct	18 ms	5156 KB	Output is correct
10	Correct	17 ms	5176 KB	Output is correct
11	Correct	17 ms	5048 KB	Output is correct
12	Correct	5 ms	2324 KB	Output is correct
13	Correct	5 ms	2412 KB	Output is correct
14	Correct	5 ms	2160 KB	Output is correct
15	Correct	5 ms	2296 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	5572 KB	Output is correct
2	Correct	35 ms	5568 KB	Output is correct
3	Correct	33 ms	5676 KB	Output is correct
4	Correct	20 ms	4284 KB	Output is correct
5	Correct	22 ms	4920 KB	Output is correct
6	Correct	22 ms	4536 KB	Output is correct
7	Correct	22 ms	4552 KB	Output is correct
8	Correct	20 ms	4408 KB	Output is correct
9	Correct	22 ms	4468 KB	Output is correct
10	Correct	18 ms	4160 KB	Output is correct
11	Correct	20 ms	4116 KB	Output is correct
12	Correct	20 ms	3888 KB	Output is correct
13	Correct	20 ms	3964 KB	Output is correct
14	Correct	20 ms	4024 KB	Output is correct
15	Correct	20 ms	4152 KB	Output is correct
16	Correct	20 ms	4316 KB	Output is correct
17	Correct	20 ms	4024 KB	Output is correct
18	Correct	20 ms	4048 KB	Output is correct
19	Correct	20 ms	4152 KB	Output is correct
20	Correct	17 ms	4672 KB	Output is correct
21	Correct	16 ms	4544 KB	Output is correct
22	Correct	20 ms	4436 KB	Output is correct
23	Correct	20 ms	4420 KB	Output is correct
24	Correct	22 ms	4464 KB	Output is correct
25	Correct	22 ms	4460 KB	Output is correct
26	Correct	22 ms	4416 KB	Output is correct
27	Correct	22 ms	4796 KB	Output is correct
28	Correct	25 ms	4408 KB	Output is correct
29	Correct	20 ms	4372 KB	Output is correct
30	Correct	20 ms	4480 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	5440 KB	Output is correct
2	Correct	33 ms	5640 KB	Output is correct
3	Correct	33 ms	5440 KB	Output is correct
4	Correct	20 ms	4160 KB	Output is correct
5	Correct	23 ms	5096 KB	Output is correct
6	Correct	23 ms	4408 KB	Output is correct
7	Correct	24 ms	4284 KB	Output is correct
8	Correct	20 ms	4588 KB	Output is correct
9	Correct	24 ms	4492 KB	Output is correct
10	Correct	20 ms	4028 KB	Output is correct
11	Correct	19 ms	3896 KB	Output is correct
12	Correct	19 ms	4008 KB	Output is correct
13	Correct	20 ms	4016 KB	Output is correct
14	Correct	20 ms	4024 KB	Output is correct
15	Correct	20 ms	4160 KB	Output is correct
16	Correct	20 ms	4168 KB	Output is correct
17	Correct	20 ms	4160 KB	Output is correct
18	Correct	20 ms	4160 KB	Output is correct
19	Correct	20 ms	4024 KB	Output is correct
20	Correct	17 ms	4424 KB	Output is correct
21	Correct	19 ms	4436 KB	Output is correct
22	Correct	31 ms	4372 KB	Output is correct
23	Correct	22 ms	4552 KB	Output is correct
24	Correct	20 ms	4280 KB	Output is correct
25	Correct	20 ms	4280 KB	Output is correct
26	Correct	22 ms	4352 KB	Output is correct
27	Correct	22 ms	4540 KB	Output is correct
28	Correct	22 ms	4536 KB	Output is correct
29	Correct	20 ms	4396 KB	Output is correct
30	Correct	20 ms	4468 KB	Output is correct
31	Correct	6 ms	2188 KB	Output is correct
32	Correct	6 ms	2304 KB	Output is correct
33	Correct	6 ms	2436 KB	Output is correct
34	Correct	6 ms	2164 KB	Output is correct
35	Correct	6 ms	2412 KB	Output is correct
36	Correct	6 ms	2428 KB	Output is correct
37	Correct	6 ms	2432 KB	Output is correct
38	Correct	7 ms	2192 KB	Output is correct
39	Correct	6 ms	2164 KB	Output is correct
40	Correct	6 ms	2320 KB	Output is correct
41	Correct	6 ms	2300 KB	Output is correct
42	Correct	6 ms	2292 KB	Output is correct

답안 #137034

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