oj.uz

Submission #647020

# Submission time Handle Problem Language Result Execution time Memory
647020 2022-10-01T11:22:41 Z Tudy006 Speedrun (RMI21_speedrun) C++14
100 / 100
 137 ms 764 KB 
#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;

const int NMAX = 1000;


vector <int> edges[NMAX + 1];
int p[NMAX + 1];
vector <int> ord;
int nxt[NMAX + 1];

void dfs( int node, int father ) {
    p[node] = father;
    ord.push_back( node );
    for ( auto it : edges[node] ) {
        if ( it == father ) continue;
        dfs( it, node );
    }
}
void assignHints( int subtask, int n, int a[], int b[] ) {
    for ( int i = 1; i < n; i ++ ) {
        edges[a[i]].push_back( b[i] );
        edges[b[i]].push_back( a[i] );
    }
    dfs( 1, 0 );
    for ( int i = 0; i < n; i ++ ) nxt[ord[i]] = ord[( i + 1 ) % n];
    setHintLen( 20 );
    for ( int i = 1; i <= n; i ++ ) {
        for ( int j = 9; j >= 0; j -- ) {
            if ( p[i] & ( 1 << j ) )
                setHint( i, 10 - j, 1 );
        }
        for ( int j = 9; j >= 0; j -- ) {
            if ( nxt[i] & ( 1 << j ) )
                setHint( i, 20 - j, 1 );
        }
    }
}
int getp() {
    int f = 0;
    for ( int i = 1; i <= 10; i ++ ) f = f * 2 + getHint( i );
    return f;
}
int getnxt() {
    int x = 0;
    for ( int i = 11; i <= 20; i ++ ) x = x * 2 + getHint( i );
    return x;
}
void speedrun( int subtask, int n, int node ) {
    int f;
    while ( ( f = getp() ) != 0 ) {
        goTo( f );
        node = f;
    }
    do {
        int x = getnxt();
        if ( goTo( x ) ) {
            node = x;
        } else {
            do {
                f = getp();
                goTo( f );
                node = f;
            } while ( !goTo( x ) );
            node = x;
        }
    } while ( getnxt() != 1 );
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 736 KB Output is correct
2 Correct 115 ms 712 KB Output is correct
3 Correct 56 ms 736 KB Output is correct
4 Correct 112 ms 720 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 724 KB Output is correct
2 Correct 92 ms 692 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 672 KB Output is correct
2 Correct 89 ms 700 KB Output is correct
3 Correct 108 ms 720 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 764 KB Output is correct
2 Correct 127 ms 712 KB Output is correct
3 Correct 111 ms 672 KB Output is correct
4 Correct 110 ms 680 KB Output is correct
5 Correct 135 ms 672 KB Output is correct
6 Correct 114 ms 684 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 716 KB Output is correct
2 Correct 94 ms 672 KB Output is correct
3 Correct 115 ms 720 KB Output is correct
4 Correct 111 ms 696 KB Output is correct
5 Correct 125 ms 716 KB Output is correct
6 Correct 137 ms 672 KB Output is correct
7 Correct 120 ms 736 KB Output is correct