oj.uz

Submission #122859

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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