oj.uz

Submission #212178

# Submission time Handle Problem Language Result Execution time Memory
212178 2020-03-22T12:13:11 Z DodgeBallMan Amusement Park (JOI17_amusement_park) C++14
100 / 100
 76 ms 25540 KB 
#include <bits/stdc++.h>
#include <Joi.h>
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e4 + 10;
vector<pii> t[N], e, tre, init;
vector<int> g[N];
int par[N], id[N], re[N], deg[N], idx, n, m;

void dfs( int u, int p ) { id[u] = idx++; for( int v : g[u] ) if( v != p ) dfs( v, u ); }
int find( int u ) { return u == par[u] ? u : par[u] = find( par[u] ); }

void extend_tree( int u, int p ) {
    if( !t[u].empty() ) return;
    int leaf;
    vector<pii> tree = t[p];
    for( pii e : tree ) ++deg[e.x], ++deg[e.y];
    for( pii e : tree ) {
        int a, b; tie( a, b ) = e;
        if( deg[a] == 1 && a != p ) { leaf = a; break; }
        if( deg[b] == 1 && b != p ) { leaf = b; break; }
    }
    re[u] = re[leaf];
    for( pii e : tree ) {
        --deg[e.x], --deg[e.y];
        if( e.x == leaf || e.y == leaf ) continue;
        t[u].emplace_back( e );
    }
    t[u].emplace_back( u, p );
    for( int v : g[u] ) if( v != p ) extend_tree( v, u );
}

void Joi( int N, int M, int A[], int B[], long long X, int T ) {
    n = N, m = M;
    iota( par, par + N, 0 );
    for( int i = 0 ; i < m ; i++ ) e.emplace_back( pii( A[i], B[i] ) );
    for( pii x : e ) {
        int a = find( x.x ), b = find( x.y );
        if( a != b ) {
            par[a] = b;
            g[x.x].emplace_back( x.y );
            g[x.y].emplace_back( x.x );
            tre.emplace_back( x );
        }
    }
    dfs( 0, 0 );
    for( pii e : tre ) if( id[e.x] < 60 && id[e.y] < 60 ) init.emplace_back( e );
    for( int i = 0 ; i < n ; i++ ) if( id[i] < 60 ) {
        re[i] = id[i];
        t[i] = init;
    }
    for( int i = 0 ; i < n ; i++ ) if( id[i] < 60 ) for( int v : g[i] ) extend_tree( v, i );
    for( int i = 0 ; i < n ; i++ ) MessageBoard( i, X >> re[i] & 1 );
}

#include <bits/stdc++.h>
#include <Ioi.h>
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e4 + 10;
vector<pii> t[N], e, tre, init;
vector<int> g[N];
int par[N], id[N], re[N], deg[N], idx, n, m;
long long ans;

int find( int u ) { return u == par[u] ? u : par[u] = find( par[u] ); }
void dfs( int u, int p ) { re[u] = id[u] = idx++; for( int v : g[u] ) if( v != p ) dfs( v, u ); }

void extend_tree( int u, int p ) {
    if( !t[u].empty() ) return;
    int leaf;
    vector<pii> tree = t[p];
    for( pii e : tree ) ++deg[e.x], ++deg[e.y];
    for( pii e : tree ) {
        int a, b; tie( a, b ) = e;
        if( deg[a] == 1 && a != p ) { leaf = a; break; }
        if( deg[b] == 1 && b != p ) { leaf = b; break; }
    }
    re[u] = re[leaf];
    for( pii e : tree ) {
        --deg[e.x], --deg[e.y];
        if( e.x == leaf || e.y == leaf ) continue;
        t[u].emplace_back( e );
    }
    t[u].emplace_back( u, p );
    for( int v : g[u] ) if( v != p ) extend_tree( v, u );
}

void get_ans( int u, int p ) {
    for( int v : g[u] ) if( v != p ) {
        int nex = Move( v );
        if( nex ) ans += 1ll << re[v];
        get_ans( v, u );
        Move( u );
    }
}
long long Ioi( int N, int M, int A[], int B[], int P, int V, int T ) {
    n = N, m = M;
    iota( par, par + N, 0 );
    for( int i = 0 ; i < m ; i++ ) e.emplace_back( pii( A[i], B[i] ) );
    for( pii x : e ) {
        int a = find( x.x ), b = find( x.y );
        if( a != b ) {
            par[a] = b;
            g[x.x].emplace_back( x.y );
            g[x.y].emplace_back( x.x );
            tre.emplace_back( x );
        }
    }
    dfs( 0, 0 );
    for( pii e : tre ) if( id[e.x] < 60 && id[e.y] < 60 ) init.emplace_back( e );
    for( int i = 0 ; i < n ; i++ ) if( id[i] < 60 ) {
        re[i] = id[i];
        t[i] = init;
    }
    for( int i = 0 ; i < n ; i++ ) if( id[i] < 60 ) for( int v : g[i] ) extend_tree( v, i );
    for( int i = 0 ; i < n ; i++ ) g[i].clear();
    for( pii e : t[P] ) g[e.x].emplace_back( e.y ), g[e.y].emplace_back( e.x );
    if( V ) ans += 1ll << re[P];
    get_ans( P, P );
    return ans;
}

Compilation message

Joi.cpp: In function 'void extend_tree(int, int)':
Joi.cpp:27:20: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     re[u] = re[leaf];
             ~~~~~~~^

Ioi.cpp: In function 'void extend_tree(int, int)':
Ioi.cpp:28:20: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     re[u] = re[leaf];
             ~~~~~~~^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2000 KB Output is correct
2 Correct 10 ms 1980 KB Output is correct
3 Correct 11 ms 2272 KB Output is correct
4 Correct 10 ms 1992 KB Output is correct
5 Correct 10 ms 1976 KB Output is correct
6 Correct 10 ms 2108 KB Output is correct
7 Correct 11 ms 2256 KB Output is correct
8 Correct 10 ms 2276 KB Output is correct
9 Correct 10 ms 2192 KB Output is correct
10 Correct 10 ms 1928 KB Output is correct
11 Correct 15 ms 2280 KB Output is correct
12 Correct 10 ms 2032 KB Output is correct
13 Correct 11 ms 2192 KB Output is correct
14 Correct 11 ms 2264 KB Output is correct
15 Correct 11 ms 2284 KB Output is correct
16 Correct 10 ms 2280 KB Output is correct
17 Correct 11 ms 2284 KB Output is correct
18 Correct 12 ms 2404 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 15504 KB Output is correct
2 Correct 70 ms 15496 KB Output is correct
3 Correct 70 ms 15372 KB Output is correct
4 Correct 61 ms 14492 KB Output is correct
5 Correct 63 ms 19648 KB Output is correct
6 Correct 61 ms 17876 KB Output is correct
7 Correct 62 ms 18144 KB Output is correct
8 Correct 68 ms 18916 KB Output is correct
9 Correct 62 ms 19104 KB Output is correct
10 Correct 56 ms 14604 KB Output is correct
11 Correct 59 ms 14468 KB Output is correct
12 Correct 57 ms 13244 KB Output is correct
13 Correct 54 ms 13252 KB Output is correct
14 Correct 59 ms 13752 KB Output is correct
15 Correct 59 ms 14508 KB Output is correct
16 Correct 61 ms 14628 KB Output is correct
17 Correct 61 ms 14364 KB Output is correct
18 Correct 59 ms 14396 KB Output is correct
19 Correct 59 ms 14496 KB Output is correct
20 Correct 57 ms 20228 KB Output is correct
21 Correct 56 ms 19948 KB Output is correct
22 Correct 61 ms 17296 KB Output is correct
23 Correct 63 ms 18920 KB Output is correct
24 Correct 62 ms 17816 KB Output is correct
25 Correct 62 ms 18348 KB Output is correct
26 Correct 64 ms 19108 KB Output is correct
27 Correct 62 ms 18984 KB Output is correct
28 Correct 63 ms 19364 KB Output is correct
29 Correct 56 ms 17188 KB Output is correct
30 Correct 60 ms 17604 KB Output is correct
31 Correct 10 ms 1980 KB Output is correct
32 Correct 10 ms 2092 KB Output is correct
33 Correct 10 ms 2284 KB Output is correct
34 Correct 11 ms 1984 KB Output is correct
35 Correct 10 ms 1988 KB Output is correct
36 Correct 10 ms 2016 KB Output is correct
37 Correct 10 ms 1928 KB Output is correct
38 Correct 10 ms 2048 KB Output is correct
39 Correct 10 ms 2040 KB Output is correct
40 Correct 10 ms 2016 KB Output is correct
41 Correct 10 ms 1800 KB Output is correct
42 Correct 10 ms 2008 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2012 KB Output is correct
2 Correct 10 ms 2004 KB Output is correct
3 Correct 10 ms 2000 KB Output is correct
4 Correct 18 ms 5560 KB Output is correct
5 Correct 18 ms 5568 KB Output is correct
6 Correct 17 ms 5568 KB Output is correct
7 Correct 17 ms 5596 KB Output is correct
8 Correct 18 ms 5548 KB Output is correct
9 Correct 57 ms 25408 KB Output is correct
10 Correct 57 ms 25540 KB Output is correct
11 Correct 56 ms 25292 KB Output is correct
12 Correct 10 ms 2040 KB Output is correct
13 Correct 10 ms 2024 KB Output is correct
14 Correct 10 ms 1796 KB Output is correct
15 Correct 10 ms 2016 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 15492 KB Output is correct
2 Correct 70 ms 15576 KB Output is correct
3 Correct 70 ms 15612 KB Output is correct
4 Correct 62 ms 14508 KB Output is correct
5 Correct 67 ms 22712 KB Output is correct
6 Correct 63 ms 19100 KB Output is correct
7 Correct 63 ms 18832 KB Output is correct
8 Correct 61 ms 16932 KB Output is correct
9 Correct 64 ms 17592 KB Output is correct
10 Correct 59 ms 14460 KB Output is correct
11 Correct 57 ms 14472 KB Output is correct
12 Correct 57 ms 13220 KB Output is correct
13 Correct 54 ms 13480 KB Output is correct
14 Correct 56 ms 13932 KB Output is correct
15 Correct 59 ms 14512 KB Output is correct
16 Correct 63 ms 14504 KB Output is correct
17 Correct 59 ms 14396 KB Output is correct
18 Correct 61 ms 14388 KB Output is correct
19 Correct 60 ms 14468 KB Output is correct
20 Correct 63 ms 20224 KB Output is correct
21 Correct 56 ms 19948 KB Output is correct
22 Correct 62 ms 18604 KB Output is correct
23 Correct 62 ms 18124 KB Output is correct
24 Correct 65 ms 18112 KB Output is correct
25 Correct 61 ms 19132 KB Output is correct
26 Correct 62 ms 18636 KB Output is correct
27 Correct 62 ms 19680 KB Output is correct
28 Correct 62 ms 17544 KB Output is correct
29 Correct 57 ms 17040 KB Output is correct
30 Correct 59 ms 17848 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 15460 KB Output is correct
2 Correct 76 ms 15604 KB Output is correct
3 Correct 70 ms 15376 KB Output is correct
4 Correct 59 ms 14496 KB Output is correct
5 Correct 63 ms 24072 KB Output is correct
6 Correct 62 ms 17608 KB Output is correct
7 Correct 61 ms 17332 KB Output is correct
8 Correct 63 ms 19368 KB Output is correct
9 Correct 62 ms 18324 KB Output is correct
10 Correct 56 ms 14612 KB Output is correct
11 Correct 56 ms 14472 KB Output is correct
12 Correct 57 ms 13236 KB Output is correct
13 Correct 55 ms 13204 KB Output is correct
14 Correct 57 ms 13748 KB Output is correct
15 Correct 60 ms 14496 KB Output is correct
16 Correct 60 ms 14496 KB Output is correct
17 Correct 59 ms 14500 KB Output is correct
18 Correct 62 ms 14400 KB Output is correct
19 Correct 60 ms 14508 KB Output is correct
20 Correct 56 ms 20480 KB Output is correct
21 Correct 66 ms 19968 KB Output is correct
22 Correct 62 ms 18592 KB Output is correct
23 Correct 63 ms 17844 KB Output is correct
24 Correct 62 ms 18088 KB Output is correct
25 Correct 67 ms 18340 KB Output is correct
26 Correct 64 ms 17220 KB Output is correct
27 Correct 62 ms 19884 KB Output is correct
28 Correct 62 ms 19964 KB Output is correct
29 Correct 62 ms 18452 KB Output is correct
30 Correct 60 ms 18444 KB Output is correct
31 Correct 11 ms 1988 KB Output is correct
32 Correct 10 ms 1928 KB Output is correct
33 Correct 13 ms 2260 KB Output is correct
34 Correct 11 ms 1984 KB Output is correct
35 Correct 10 ms 1980 KB Output is correct
36 Correct 10 ms 2020 KB Output is correct
37 Correct 10 ms 2024 KB Output is correct
38 Correct 10 ms 2040 KB Output is correct
39 Correct 10 ms 2040 KB Output is correct
40 Correct 10 ms 1928 KB Output is correct
41 Correct 11 ms 1992 KB Output is correct
42 Correct 10 ms 2024 KB Output is correct