Submission #504807

#	Time	Username	Problem	Language	Result	Execution time	Memory
504807		daongocha	Speedrun (RMI21_speedrun)	C++14	0 / 100	1 ms	328 KiB

speedrun

#include <bits/stdc++.h>

#include "speedrun.h"

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);
 
using namespace std;

const int MAXN = 1005;
vector<int> path[MAXN];
vector<int> order;
int parent[MAXN];

// void assignHints(int subtask, int N, int A[], int B[]);
// void speedrun(int subtask, int N, int start);

// void setHintLen(int l);
// void setHint(int i, int j, bool b);
// int getLength();
// bool getHint(int j);
// bool goTo(int x);

void dfs(int u, int pre = 0) {
    cout << u << endl;
    order.push_back(u);
    parent[u] = pre;
    for (int v: path[u])
        if (v != pre) dfs(v, u);
}

void assignHints(int sub, int n, int A[], int B[]) {
    for (int i = 1; i < n; i++) {
        int u = A[i], v = B[i];
        path[u].push_back(v);
        path[v].push_back(u);
    }
    
    dfs(1);

    setHintLen(20);
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i], v = (i + 1 >= n ? 0 : order[i + 1]);
        for (int j = 1; j <= 10; j++)
            setHint(u, j - 1, (v >> (j - 1) & 1));

        for (int j = 11; j <= 20; j++)
            setHint(u, j - 1, (parent[u] >> (j - 11) & 1));
    }
}

int nxt[MAXN], par[MAXN];
bool passed[MAXN];
int cnt = 0;
int tot;

void solve(int u, int go) {
    // cout << u << ' ' << go << endl;
    assert(u);
    if (!passed[u]) {
        passed[u] = 1;
        cnt++;
        for (int j = 0; j < 10; j++)
            nxt[u] |= (getHint(j) << j);

        for (int j = 0; j < 10; j++) 
            par[u] |= (getHint(j + 10) << j);

        if (!passed[nxt[u]]) go = nxt[u];
    }

    if (cnt == tot) return;

    if (!go || !goTo(go)) goTo(par[u]), solve(par[u], go);
    else solve(go, 0);
}

void speedrun(int sub, int n, int start) {
    tot = n;
    solve(start, 0);
}

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