oj.uz

Submission #137027

# Submission time Handle Problem Language Result Execution time Memory
137027 2019-07-26T23:10:05 Z osaaateiasavtnl Amusement Park (JOI17_amusement_park) C++14
73 / 100
 34 ms 6100 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], mem[N];
int vert[60];
int ans[N];
int CUR = -1;
void dfs1(int u, int p) {
    if (vis == 60) return;
    ++vis;              
    int b = tin[u] % 60;
    want[u] = vert[b] == -1;
    bool want0 = want[u];
    for (int v : tree[u]) {
        dfs1(v, u);
        want[u] |= want[v];
        mem[u] |= mem[v];
    }   
    mem[u] |= !want0 && want[u];
}   
bool comp(int u, int v) {
    return mem[u] < mem[v];
}   
void check(int v) {
    bool c = 0;
    for (int e : g[CUR]) {
        c |= e == v;
    }   
    if (!c) exit(1);
}   
void dfs2(int u, int p) {
    if (tree[u].empty()) return;
    sort(tree[u].begin(), tree[u].end(), comp);
    for (int v : tree[u]) {
        if (want[v]) {
            vert[tin[v] % 60] = v;

            check(v);
            ans[v] = move(v);
            CUR = v;

            dfs2(v, u);
            if (!mem[v]) {
                check(u);
                move(u);
                CUR = 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]);
    CUR = u;
    if (want[u]) dfs2(u, par[u]);
    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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2288 KB Output is correct
2 Correct 5 ms 2160 KB Output is correct
3 Correct 5 ms 2168 KB Output is correct
4 Correct 5 ms 2160 KB Output is correct
5 Correct 5 ms 2160 KB Output is correct
6 Correct 5 ms 2412 KB Output is correct
7 Correct 5 ms 2168 KB Output is correct
8 Correct 5 ms 2304 KB Output is correct
9 Correct 5 ms 2296 KB Output is correct
10 Correct 5 ms 2160 KB Output is correct
11 Correct 8 ms 2468 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 2168 KB Output is correct
15 Correct 5 ms 2172 KB Output is correct
16 Correct 6 ms 2172 KB Output is correct
17 Correct 6 ms 2436 KB Output is correct
18 Correct 6 ms 2372 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5784 KB Output is correct
2 Correct 34 ms 5760 KB Output is correct
3 Correct 33 ms 5760 KB Output is correct
4 Correct 20 ms 4248 KB Output is correct
5 Correct 22 ms 4784 KB Output is correct
6 Correct 22 ms 4596 KB Output is correct
7 Correct 20 ms 4556 KB Output is correct
8 Correct 24 ms 4596 KB Output is correct
9 Correct 20 ms 4760 KB Output is correct
10 Correct 20 ms 4252 KB Output is correct
11 Correct 20 ms 4132 KB Output is correct
12 Correct 19 ms 3972 KB Output is correct
13 Correct 20 ms 4108 KB Output is correct
14 Correct 20 ms 4108 KB Output is correct
15 Correct 22 ms 4376 KB Output is correct
16 Correct 20 ms 4384 KB Output is correct
17 Correct 20 ms 4196 KB Output is correct
18 Correct 20 ms 4248 KB Output is correct
19 Runtime error 24 ms 4184 KB Execution failed because the return code was nonzero
20 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2304 KB Output is correct
2 Correct 5 ms 2164 KB Output is correct
3 Correct 5 ms 2164 KB Output is correct
4 Correct 8 ms 2848 KB Output is correct
5 Correct 7 ms 2720 KB Output is correct
6 Correct 7 ms 2852 KB Output is correct
7 Correct 7 ms 2720 KB Output is correct
8 Correct 7 ms 2720 KB Output is correct
9 Correct 18 ms 5400 KB Output is correct
10 Correct 18 ms 5400 KB Output is correct
11 Correct 18 ms 5536 KB Output is correct
12 Correct 5 ms 2328 KB Output is correct
13 Correct 5 ms 2292 KB Output is correct
14 Correct 5 ms 2552 KB Output is correct
15 Correct 5 ms 2176 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5888 KB Output is correct
2 Correct 33 ms 5896 KB Output is correct
3 Correct 34 ms 6100 KB Output is correct
4 Correct 20 ms 4288 KB Output is correct
5 Correct 22 ms 5228 KB Output is correct
6 Correct 22 ms 4768 KB Output is correct
7 Correct 20 ms 4688 KB Output is correct
8 Correct 20 ms 4384 KB Output is correct
9 Correct 22 ms 4592 KB Output is correct
10 Correct 20 ms 4388 KB Output is correct
11 Correct 20 ms 4384 KB Output is correct
12 Correct 20 ms 4248 KB Output is correct
13 Correct 19 ms 3968 KB Output is correct
14 Correct 20 ms 4192 KB Output is correct
15 Correct 20 ms 4384 KB Output is correct
16 Correct 22 ms 4248 KB Output is correct
17 Correct 20 ms 4120 KB Output is correct
18 Correct 20 ms 4276 KB Output is correct
19 Correct 22 ms 4280 KB Output is correct
20 Correct 18 ms 4784 KB Output is correct
21 Correct 19 ms 4640 KB Output is correct
22 Correct 23 ms 4640 KB Output is correct
23 Correct 22 ms 4584 KB Output is correct
24 Correct 24 ms 4508 KB Output is correct
25 Correct 20 ms 4716 KB Output is correct
26 Correct 22 ms 4696 KB Output is correct
27 Correct 20 ms 4612 KB Output is correct
28 Correct 20 ms 4728 KB Output is correct
29 Correct 20 ms 4376 KB Output is correct
30 Correct 20 ms 4728 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5760 KB Output is correct
2 Correct 33 ms 5900 KB Output is correct
3 Correct 33 ms 5900 KB Output is correct
4 Correct 20 ms 4256 KB Output is correct
5 Correct 22 ms 5352 KB Output is correct
6 Correct 20 ms 4588 KB Output is correct
7 Correct 22 ms 4640 KB Output is correct
8 Correct 24 ms 4768 KB Output is correct
9 Correct 20 ms 4640 KB Output is correct
10 Correct 20 ms 4124 KB Output is correct
11 Correct 20 ms 4376 KB Output is correct
12 Correct 20 ms 3728 KB Output is correct
13 Correct 20 ms 4104 KB Output is correct
14 Correct 20 ms 4168 KB Output is correct
15 Correct 23 ms 4248 KB Output is correct
16 Correct 22 ms 4420 KB Output is correct
17 Correct 22 ms 4244 KB Output is correct
18 Correct 22 ms 4376 KB Output is correct
19 Correct 23 ms 4120 KB Output is correct
20 Correct 18 ms 4660 KB Output is correct
21 Correct 18 ms 4660 KB Output is correct
22 Correct 22 ms 4640 KB Output is correct
23 Correct 22 ms 4592 KB Output is correct
24 Correct 23 ms 4508 KB Output is correct
25 Correct 22 ms 4640 KB Output is correct
26 Correct 20 ms 4512 KB Output is correct
27 Correct 22 ms 4792 KB Output is correct
28 Correct 20 ms 4692 KB Output is correct
29 Correct 20 ms 4352 KB Output is correct
30 Correct 20 ms 4492 KB Output is correct
31 Runtime error 5 ms 2240 KB Execution failed because the return code was nonzero
32 Halted 0 ms 0 KB -