Submission #1199576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199576		badge881	Speedrun (RMI21_speedrun)	C++20	100 / 100	56 ms	516 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
int n, tin[maxn], et[maxn];
int timer;
int par[maxn];
vector<int> g[maxn];

void dfs(int u, int prev)
{
    tin[u] = ++timer;
    et[timer] = u;
    for (auto v : g[u])
    {
        if (v == prev)
            continue;
        par[v] = u;
        dfs(v, u);
    }
}

void assignHints(int subtask, int N, int A[], int B[])
{
    n = N;
    for (int i = 1; i <= n; ++i)
        g[i].clear();
    for (int i = 1; i < n; ++i)
    {
        int u = A[i], v = B[i];
        g[u].push_back(v);
        g[v].push_back(u);
    }
    timer = par[1] = 0;
    dfs(1, 0);
    setHintLen(20);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < 10; ++j)
            setHint(i, j + 1, (par[i] >> j & 1));

        int t = tin[i];
        if (t < n)
        {
            t = et[t + 1];
            for (int j = 0; j < 10; ++j)
                setHint(i, j + 1 + 10, (t >> j & 1));
        }
    }
}

int getp()
{
    int p = 0;
    for (int i = 0; i < 10; ++i)
        if (getHint(i + 1))
            p |= (1 << i);
    return p;
}

int gets()
{
    int p = 0;
    for (int i = 0; i < 10; ++i)
        if (getHint(i + 1 + 10))
            p |= (1 << i);
    return p;
}

void speedrun(int subtask, int N, int start)
{
    n = N;
    vector<bool> vis(n + 1);
    vis[start] = 1;
    while (true)
    {
        int p = getp();
        if (!p)
            break;
        goTo(p);
    }
    while (true)
    {
        int nxt = gets();
        if (!nxt)
            break;
        while (!goTo(nxt))
            goTo(getp());
    }
}

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40