oj.uz

Submission #503693

# Submission time Handle Problem Language Result Execution time Memory
503693 2022-01-08T15:36:24 Z blue Speedrun (RMI21_speedrun) C++17
100 / 100
 130 ms 920 KB 
#include "speedrun.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

using vi = vector<int>;
using vvi = vector<int>;
#define sz(x) int(x.size())

const int maxN = 1'000;


vi visit(1+maxN, 0);
vi edge[1+maxN];
vi ord;
vi par(1+maxN, 0);

void dfs(int u, int p)
{
    par[u] = p;
    ord.push_back(u);
    for(int v: edge[u])
    {
        if(v == p) continue;
        dfs(v, u);
    }
}

void assignHints(int subtask, int N, int A[], int B[])
{
    // cerr << "assign called\n";
    for(int e = 1; e <= N-1; e++)
    {
        edge[A[e]].push_back(B[e]);
        edge[B[e]].push_back(A[e]);
    }
    dfs(1, 0);

    setHintLen(20);

    for(int u = 1; u <= N; u++)
        for(int b = 0; b < 10; b++)
            if(par[u] & (1 << b))
                setHint(u, b+1, 1);

    for(int x = 0; x < N; x++)
    {
        int u = ord[x];
        int v = ord[(x+1)%N];

        for(int b = 0; b < 10; b++)
            if(v & (1 << b))
                setHint(u, b+11, 1);
    }

    // cerr << "assigned!\n";

    // for(int u = 1; u <= N; u++) cerr << "par " << u << " = " << par[u] << '\n';
}

void speedrun(int subtask, int N, int curr)
{
    int z = 0;

    vi visit(1+N, 0);
    visit[curr] = 1;
    int visit_count = 1;

    // cerr << "curr = " << curr << '\n';

    while(visit_count < N)
    {
        // cerr << "start visit count = " << visit_count << '\n';
        int target = 0;
        for(int b = 0; b < 10; b++)
            target += (1 << b) * getHint(11+b);

        // cerr << "next target = " << target << '\n';

        while(1)
        {
            // cerr << "visit count = " << visit_count << '\n';
            // z++;
            // if(z > 20) break;
            if(goTo(target))
            {
                // cerr << "! travelled to " << target << '\n';
                if(!visit[target]) visit_count++;
                // cerr << visit_count << '\n';
                visit[target] = 1;
                curr = target;
                // cerr << "1curr = " << curr << '\n';
                break;
            }

            // cerr << "21curr = " << curr << '\n';

            int par = 0;
            for(int b = 0; b < 10; b++)
                par += (1<<b) * getHint(1+b);

            // cerr << "par = " << par << '\n';

            goTo(par);
            // cerr << "op = " << goTo(par) << '\n';
            // cerr << "travelled to " << par << '\n';
            curr = par;
            // cerr << "2curr = " << curr << '\n';
        }
        // if(z > 20) break;
    }
}

Compilation message

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:64:9: warning: unused variable 'z' [-Wunused-variable]
   64 |     int z = 0;
      |         ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 792 KB Output is correct
2 Correct 111 ms 720 KB Output is correct
3 Correct 130 ms 836 KB Output is correct
4 Correct 100 ms 668 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 700 KB Output is correct
2 Correct 109 ms 708 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 920 KB Output is correct
2 Correct 119 ms 832 KB Output is correct
3 Correct 128 ms 660 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 660 KB Output is correct
2 Correct 97 ms 704 KB Output is correct
3 Correct 99 ms 828 KB Output is correct
4 Correct 102 ms 676 KB Output is correct
5 Correct 101 ms 660 KB Output is correct
6 Correct 118 ms 700 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 704 KB Output is correct
2 Correct 114 ms 788 KB Output is correct
3 Correct 122 ms 704 KB Output is correct
4 Correct 124 ms 692 KB Output is correct
5 Correct 106 ms 660 KB Output is correct
6 Correct 125 ms 668 KB Output is correct
7 Correct 68 ms 704 KB Output is correct