Submission #1129098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129098		LucaIlie	Amusement Park (JOI17_amusement_park)	C++20	79 / 100	23 ms	2376 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;

namespace JOI {
    const int MAX_N = 1e4;
    const int MAX_M = 2e4;
    const int K = 60;

    int n, m;
    bool isTreeDeep = true;
    bool vis[MAX_N], isSpecial[MAX_N], message[MAX_N];
    int depth[MAX_N], maxDepth[MAX_N], deepestSon[MAX_N], parent[MAX_N];
    vector<int> specials;
    pair<int, int> edges[MAX_M];
    vector<int> adj[MAX_N];

    void getDepths( int u ) {
        vis[u] = true;
        maxDepth[u] = depth[u];
        for ( int v: adj[u] ) {
            if ( vis[v] )
                continue;
            depth[v] = depth[u] + 1;
            parent[v] = u;
            getDepths( v );
            if ( maxDepth[v] > maxDepth[u] ) {
                deepestSon[u] = v;
                maxDepth[u] = maxDepth[v];
            }
        }
    }

    void getSpecials( int u ) {
        vis[u] = true;
        if ( specials.size() == K )
            return;

        if ( !isSpecial[u] ) {
            specials.push_back( u );
            isSpecial[u] = true;
        }
        for ( int v: adj[u] ) {
            if ( vis[v] )
                continue;
            getSpecials( v );
        }
    }

    void proccessTree( int N, int M, int A[], int B[] ) {
        n = N;
        m = M;
        for ( int i = 0; i < m; i++ )
            edges[i] = { A[i], B[i] };
        sort( edges, edges + m );
        for ( int i = 0; i < m; i++ ) {
            adj[edges[i].first].push_back( edges[i].second );
            adj[edges[i].second].push_back( edges[i].first );
        }

        getDepths( 0 );

        int deepestVertex = 0;
        for ( int v = 1; v < n; v++ ) {
            if ( depth[v] > depth[deepestVertex] )
                deepestVertex = v;
        }

        if ( depth[deepestVertex] < K - 1 ) {
            isTreeDeep = false;
            for ( int v = 0; v < n; v++ )
                vis[v] = false;
            int v = deepestVertex;
            while ( v != 0 ) {
                isSpecial[v] = true;
                specials.push_back( v );
                v = parent[v];
            }
            getSpecials( 0 );
            assert( specials.size() >= K );
        }
    }
}

using namespace JOI;

void Joi( int N, int M, int A[], int B[], long long x, int T ) {
    proccessTree( N, M, A, B );

    if ( isTreeDeep ) {
        //printf( "DEEP TREE\n" );
        for ( int v = 0; v < n; v++ )
            message[v] = ((x >> (K - 1 - depth[v] % K)) & 1);
    } else {
        //printf( "NOT DEEP TREE\n" );
        for ( int i = 0; i < K; i++ )
            message[specials[i]] = ((x >> i) & 1);
    }
    for ( int v = 0; v < n; v++ )
        MessageBoard( v, message[v] );
    /*for ( int v = 0; v < n; v++ )
        printf( "%d %d\n", v, message[v] );*/
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>

using namespace std;

namespace IOI {
    const int MAX_N = 1e4;
    const int MAX_M = 2e4;
    const int K = 60;

    int n, m;
    bool isTreeDeep = true;
    bool vis[MAX_N], isSpecial[MAX_N], message[MAX_N];
    int depth[MAX_N], maxDepth[MAX_N], deepestSon[MAX_N], parent[MAX_N];
    vector<int> specials;
    pair<int, int> edges[MAX_M];
    vector<int> adj[MAX_N];

    void getDepths( int u ) {
        vis[u] = true;
        maxDepth[u] = depth[u];
        for ( int v: adj[u] ) {
            if ( vis[v] )
                continue;
            depth[v] = depth[u] + 1;
            parent[v] = u;
            getDepths( v );
            if ( maxDepth[v] > maxDepth[u] ) {
                deepestSon[u] = v;
                maxDepth[u] = maxDepth[v];
            }
        }
    }

    void getSpecials( int u ) {
        vis[u] = true;
        if ( specials.size() == K )
            return;

        if ( !isSpecial[u] ) {
            specials.push_back( u );
            isSpecial[u] = true;
        }
        for ( int v: adj[u] ) {
            if ( vis[v] )
                continue;
            getSpecials( v );
        }
    }

    void proccessTree( int N, int M, int A[], int B[] ) {
        n = N;
        m = M;
        for ( int i = 0; i < m; i++ )
            edges[i] = { A[i], B[i] };
        sort( edges, edges + m );
        for ( int i = 0; i < m; i++ ) {
            adj[edges[i].first].push_back( edges[i].second );
            adj[edges[i].second].push_back( edges[i].first );
        }

        getDepths( 0 );

        int deepestVertex = 0;
        for ( int v = 1; v < n; v++ ) {
            if ( depth[v] > depth[deepestVertex] )
                deepestVertex = v;
        }

        if ( depth[deepestVertex] < K - 1 ) {
            isTreeDeep = false;
            for ( int v = 0; v < n; v++ )
                vis[v] = false;
            int v = deepestVertex;
            while ( v != 0 ) {
                isSpecial[v] = true;
                specials.push_back( v );
                v = parent[v];
            }
            getSpecials( 0 );
            assert( specials.size() >= K );
        }
    }
}

using namespace IOI;

void discoverSpecials( int u ) {
    vis[u] = true;
    for ( int v: adj[u] ) {
        if ( vis[v] || !isSpecial[v] )
            continue;
        int b = Move( v );
        message[v] = b;
        discoverSpecials( v );
        Move( u );
    }
}

long long Ioi( int N, int M, int A[], int B[], int P, int V, int T ) {
    proccessTree( N, M, A, B );

    int v = P, b = V;
    long long x = 0;
    if ( isTreeDeep ) {
        //printf( "DEEP TREE\n" );
        if ( depth[v] >= K ) {
            x += ((long long)b << (K - 1 - depth[v] % K));
            for ( int i = 0; i < K - 1; i++ ) {
                v = parent[v];
                b = Move( v );
                x += ((long long)b << (K - 1 - depth[v] % K));
            }
        } else {
            message[v] = b;
            while ( v != 0 ) {
                v = parent[v];
                b = Move( v );
                message[v] = b;
            }
            x += ((long long)b << (K - 1 - depth[v] % K));
            for ( int i = 0; i < K - 1; i++ ) {
                v = deepestSon[v];
                b = Move( v );
                x += ((long long)b << (K - 1 - depth[v] % K));
            }
        }
    } else {
        //printf( "NOT DEPP TREE\n" );
        message[v] = b;
        while ( v != 0 ) {
            v = parent[v];
            b = Move( v );
            message[v] = b;
        }
        for ( int v = 0; v < n; v++ )
            vis[v] = false;
        discoverSpecials( 0 );
        for ( int i = 0; i < specials.size(); i++ )
            x += ((long long)message[specials[i]] << i);
    }
    /*for ( int v = 0; v < n; v++ )
        printf( "%d %d\n", v, message[v] );
    printf( "%lld\n", x );*/

    return x;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 51 / 55
• Subtask 5: 0 / 17