oj.uz

Submission #212177

# Submission time Handle Problem Language Result Execution time Memory
212177 2020-03-22T12:10:20 Z DodgeBallMan Amusement Park (JOI17_amusement_park) C++14
10 / 100
 158 ms 262148 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 );
            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 );
            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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2020 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 158 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1996 KB Output is correct
2 Correct 10 ms 1972 KB Output is correct
3 Correct 10 ms 2000 KB Output is correct
4 Correct 16 ms 5588 KB Output is correct
5 Correct 16 ms 5600 KB Output is correct
6 Correct 18 ms 5644 KB Output is correct
7 Correct 18 ms 5540 KB Output is correct
8 Correct 17 ms 5596 KB Output is correct
9 Correct 56 ms 25292 KB Output is correct
10 Correct 59 ms 25320 KB Output is correct
11 Correct 57 ms 25320 KB Output is correct
12 Correct 10 ms 1888 KB Output is correct
13 Correct 10 ms 2024 KB Output is correct
14 Correct 10 ms 2048 KB Output is correct
15 Correct 10 ms 1924 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 150 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 154 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -