답안 #122859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122859	2019-06-29T11:52:56 Z	songc	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	1291 ms	61080 KB

#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

static int N, M;
static vector<int> adj[10101];
static int C[10101], num;
static set<int> G[10101];
static queue<pii> Q;

static void dfs(int u){
    if (C[u] != -1) return;
    if (num >= 60) return;
    C[u] = num++;
    for (int v : adj[u]) dfs(v);
}

static LL Color(int u, int r, int x, LL chk){
    if (C[u] == -1) return chk;
    if (chk & (1ll << C[u])) return chk;
    if (__builtin_popcountl(chk) == 59) return chk;
    if (G[x].find(u) == G[x].end()) return chk;
    chk |= 1ll << C[u];
    G[r].insert(u);
    for (int v : adj[u]) chk = Color(v, r, x, chk);
    return chk;
}

void Joi(int n, int m, int A[], int B[], long long X, int T) {
    N=n, M=m;
    for (int i=0; i<M; i++){
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    memset(C, -1, sizeof C);
    dfs(0);
    for (int i=0; i<N; i++){
        if (C[i] == -1) continue;
        for (int j=0; j<N; j++) if (C[j] != -1) G[i].insert(j);
        for (int j : adj[i]) Q.push(pii(j, i));
    }
    while (!Q.empty()){
        pii t = Q.front();
        Q.pop();
        if (C[t.first] != -1) continue;
        LL chk = 0;
        chk = Color(t.second, t.first, t.second, chk);
        G[t.first].insert(t.first);
        for (int i=0; i<60; i++) if (~chk & (1ll<<i)) C[t.first] = i;
        for (int v : adj[t.first]) Q.push(pii(v, t.first));
    }
    for (int i=0; i<N; i++) MessageBoard(i, (X & (1ll << C[i])) ? 1 : 0);
}

#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

static int N, M;
static vector<int> adj[10101];
static int C[10101], num;
static set<int> G[10101];
static LL ans;
static queue<pii> Q;

static void dfs(int u){
    if (C[u] != -1) return;
    if (num >= 60) return;
    C[u] = num++;
    for (int v : adj[u]) dfs(v);
}

static LL Color(int u, int r, int x, LL chk){
    if (C[u] == -1) return chk;
    if (chk & (1ll << C[u])) return chk;
    if (__builtin_popcountl(chk) == 59) return chk;
    if (G[x].find(u) == G[x].end()) return chk;
    chk |= 1ll << C[u];
    G[r].insert(u);
    for (int v : adj[u]) chk = Color(v, r, x, chk);
    return chk;
}

static LL Findans(int u, int p, int x, LL chk){
    if (C[u] == -1) return chk;
    if (chk & (1ll << C[u])) return chk;
    if (G[x].find(u) == G[x].end()) return chk;
    chk |= 1ll << C[u];
    if (p != -1) ans |= (LL)Move(u) << C[u];
    for (int v : adj[u]) chk = Findans(v, u, x, chk);
    if (p != -1) Move(p);
    return chk;
}

long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
    N=n, M=m;
    for (int i=0; i<M; i++){
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    memset(C, -1, sizeof C);
    dfs(0);
    for (int i=0; i<N; i++){
        if (C[i] == -1) continue;
        for (int j=0; j<N; j++) if (C[j] != -1) G[i].insert(j);
        for (int j : adj[i]) Q.push(pii(j, i));
    }
    while (!Q.empty()){
        pii t = Q.front();
        Q.pop();
        if (C[t.first] != -1) continue;
        LL chk = 0;
        chk = Color(t.second, t.first, t.second, chk);
        G[t.first].insert(t.first);
        for (int i=0; i<60; i++) if (~chk & (1ll<<i)) C[t.first] = i;
        for (int v : adj[t.first]) Q.push(pii(v, t.first));
    }
    Findans(P, -1, P, 0);
    ans |= (LL)V << C[P];
    return ans;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	2680 KB	Output is correct
2	Correct	8 ms	3248 KB	Output is correct
3	Correct	12 ms	3960 KB	Output is correct
4	Correct	8 ms	2928 KB	Output is correct
5	Correct	8 ms	2944 KB	Output is correct
6	Correct	8 ms	3212 KB	Output is correct
7	Correct	12 ms	3960 KB	Output is correct
8	Correct	11 ms	3968 KB	Output is correct
9	Correct	10 ms	3832 KB	Output is correct
10	Correct	8 ms	3184 KB	Output is correct
11	Correct	16 ms	3492 KB	Output is correct
12	Correct	6 ms	2672 KB	Output is correct
13	Correct	12 ms	4092 KB	Output is correct
14	Correct	12 ms	3960 KB	Output is correct
15	Correct	12 ms	3968 KB	Output is correct
16	Correct	12 ms	3832 KB	Output is correct
17	Correct	12 ms	3968 KB	Output is correct
18	Correct	12 ms	3960 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	325 ms	60896 KB	Output is correct
2	Correct	360 ms	61080 KB	Output is correct
3	Correct	319 ms	60912 KB	Output is correct
4	Correct	286 ms	60104 KB	Output is correct
5	Correct	316 ms	60016 KB	Output is correct
6	Correct	321 ms	60092 KB	Output is correct
7	Correct	297 ms	59948 KB	Output is correct
8	Correct	298 ms	59984 KB	Output is correct
9	Correct	295 ms	60096 KB	Output is correct
10	Correct	1272 ms	60204 KB	Output is correct
11	Correct	1258 ms	60440 KB	Output is correct
12	Correct	266 ms	54828 KB	Output is correct
13	Correct	272 ms	54900 KB	Output is correct
14	Correct	317 ms	57712 KB	Output is correct
15	Correct	386 ms	60208 KB	Output is correct
16	Correct	388 ms	60084 KB	Output is correct
17	Correct	301 ms	59984 KB	Output is correct
18	Correct	300 ms	60088 KB	Output is correct
19	Correct	303 ms	60104 KB	Output is correct
20	Correct	194 ms	60000 KB	Output is correct
21	Correct	192 ms	59244 KB	Output is correct
22	Correct	304 ms	59968 KB	Output is correct
23	Correct	297 ms	60220 KB	Output is correct
24	Correct	304 ms	60144 KB	Output is correct
25	Correct	299 ms	60144 KB	Output is correct
26	Correct	308 ms	60284 KB	Output is correct
27	Correct	304 ms	60028 KB	Output is correct
28	Correct	317 ms	60028 KB	Output is correct
29	Correct	267 ms	55088 KB	Output is correct
30	Correct	284 ms	57208 KB	Output is correct
31	Correct	8 ms	3196 KB	Output is correct
32	Correct	8 ms	3204 KB	Output is correct
33	Correct	10 ms	3968 KB	Output is correct
34	Correct	8 ms	3268 KB	Output is correct
35	Correct	6 ms	3016 KB	Output is correct
36	Correct	6 ms	2680 KB	Output is correct
37	Correct	6 ms	2680 KB	Output is correct
38	Correct	6 ms	2764 KB	Output is correct
39	Correct	6 ms	2672 KB	Output is correct
40	Correct	7 ms	2816 KB	Output is correct
41	Correct	7 ms	3000 KB	Output is correct
42	Correct	6 ms	2804 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	2904 KB	Output is correct
2	Correct	6 ms	2928 KB	Output is correct
3	Correct	6 ms	2800 KB	Output is correct
4	Correct	35 ms	11780 KB	Output is correct
5	Correct	32 ms	11536 KB	Output is correct
6	Correct	35 ms	11664 KB	Output is correct
7	Correct	37 ms	11612 KB	Output is correct
8	Correct	33 ms	11664 KB	Output is correct
9	Correct	187 ms	59192 KB	Output is correct
10	Correct	195 ms	59416 KB	Output is correct
11	Correct	201 ms	59412 KB	Output is correct
12	Correct	6 ms	2544 KB	Output is correct
13	Correct	6 ms	2544 KB	Output is correct
14	Correct	6 ms	2768 KB	Output is correct
15	Correct	6 ms	2740 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	314 ms	60984 KB	Output is correct
2	Correct	315 ms	60992 KB	Output is correct
3	Correct	312 ms	60808 KB	Output is correct
4	Correct	295 ms	60080 KB	Output is correct
5	Correct	312 ms	59992 KB	Output is correct
6	Correct	294 ms	59964 KB	Output is correct
7	Correct	327 ms	60072 KB	Output is correct
8	Correct	303 ms	59984 KB	Output is correct
9	Correct	321 ms	60124 KB	Output is correct
10	Correct	1257 ms	60220 KB	Output is correct
11	Correct	1259 ms	60480 KB	Output is correct
12	Correct	260 ms	54812 KB	Output is correct
13	Correct	260 ms	55004 KB	Output is correct
14	Correct	279 ms	57452 KB	Output is correct
15	Correct	395 ms	60036 KB	Output is correct
16	Correct	393 ms	59992 KB	Output is correct
17	Correct	296 ms	60020 KB	Output is correct
18	Correct	297 ms	59972 KB	Output is correct
19	Correct	299 ms	59960 KB	Output is correct
20	Correct	201 ms	60136 KB	Output is correct
21	Correct	205 ms	59268 KB	Output is correct
22	Correct	301 ms	59992 KB	Output is correct
23	Correct	300 ms	59992 KB	Output is correct
24	Correct	302 ms	60208 KB	Output is correct
25	Correct	330 ms	60080 KB	Output is correct
26	Correct	318 ms	60096 KB	Output is correct
27	Correct	315 ms	60220 KB	Output is correct
28	Correct	322 ms	60052 KB	Output is correct
29	Correct	289 ms	54824 KB	Output is correct
30	Correct	302 ms	57336 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	315 ms	60856 KB	Output is correct
2	Correct	314 ms	60868 KB	Output is correct
3	Correct	315 ms	60908 KB	Output is correct
4	Correct	298 ms	59968 KB	Output is correct
5	Correct	309 ms	60276 KB	Output is correct
6	Correct	332 ms	60196 KB	Output is correct
7	Correct	302 ms	59984 KB	Output is correct
8	Correct	297 ms	60004 KB	Output is correct
9	Correct	313 ms	60228 KB	Output is correct
10	Correct	1291 ms	60224 KB	Output is correct
11	Correct	1266 ms	60160 KB	Output is correct
12	Correct	267 ms	54928 KB	Output is correct
13	Correct	266 ms	55000 KB	Output is correct
14	Correct	279 ms	57648 KB	Output is correct
15	Correct	383 ms	60112 KB	Output is correct
16	Correct	388 ms	59900 KB	Output is correct
17	Correct	301 ms	60024 KB	Output is correct
18	Correct	293 ms	60108 KB	Output is correct
19	Correct	292 ms	60120 KB	Output is correct
20	Correct	196 ms	60168 KB	Output is correct
21	Correct	192 ms	59180 KB	Output is correct
22	Correct	371 ms	60068 KB	Output is correct
23	Correct	330 ms	60092 KB	Output is correct
24	Correct	309 ms	60088 KB	Output is correct
25	Correct	327 ms	60164 KB	Output is correct
26	Correct	301 ms	60016 KB	Output is correct
27	Correct	294 ms	59960 KB	Output is correct
28	Correct	294 ms	59932 KB	Output is correct
29	Correct	283 ms	54848 KB	Output is correct
30	Correct	303 ms	57216 KB	Output is correct
31	Correct	8 ms	3184 KB	Output is correct
32	Correct	9 ms	3316 KB	Output is correct
33	Correct	10 ms	3972 KB	Output is correct
34	Correct	8 ms	3184 KB	Output is correct
35	Correct	6 ms	2808 KB	Output is correct
36	Correct	6 ms	2672 KB	Output is correct
37	Correct	6 ms	2680 KB	Output is correct
38	Correct	6 ms	2544 KB	Output is correct
39	Correct	6 ms	2780 KB	Output is correct
40	Correct	6 ms	2792 KB	Output is correct
41	Correct	7 ms	2988 KB	Output is correct
42	Correct	6 ms	2544 KB	Output is correct

답안 #122859

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