Submission #1112201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112201		acoatoitgs	Speedrun (RMI21_speedrun)	C++17	0 / 100	2 ms	592 KiB

speedrun

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

vector<vector<int>> adj;
int N;
int LEN;
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    ::N = N;
    adj.resize(N);
    for(int i = 1; i < N; i++)
    {
        // cout << adj.size() << " " << A[i] << "\n";
        adj[A[i]].emplace_back(B[i]);
        adj[B[i]].emplace_back(A[i]);
    }
    LEN = floor(log2(N))+1;
    setHintLen(LEN);

    for(int i = 0; i < N; i++)
    {
        int tmp = i;
        for(int k = 0; k < LEN; k++)
        {
            setHint(i, k, tmp&1);
            tmp >>=1;
        }
    }
}

vector<int> dfsize;

int dfs(int node, int parent = -1)
{
    for(auto i : adj[node])
    {
        if(i == parent) continue;
        dfsize[i] += dfs(i, node);
    }
    return dfsize[node];
}
int vis = 0;
void solve(int node, int parent = -1)
{
    vis++;
    if(vis == N) return;
    vector<pair<int,int>> order;
    for(auto i : adj[node]) order.push_back({dfsize[i], i});

    sort(order.begin(), order.end());

    for(auto &i : order)
    {
        if(i.second == parent) continue;

        goTo(i.second);
        solve(i.second, node);
        if(vis == N) return;
    }

    goTo(parent);
}
void speedrun(int subtask, int N, int start) { /* your solution here */

    int node = 0;
    for(int k = 0; k < LEN; k++)
    {
        if(getHint(k)) node = node | (1<<k);
    }   

    //dfs size
    dfsize.resize(N, 1);
    dfs(node);

    solve(node, -1);
}

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