oj.uz

Submission #1112201

# Submission time Handle Problem Language Result Execution time Memory
1112201 2024-11-13T19:28:14 Z acoatoitgs Speedrun (RMI21_speedrun) C++17
0 / 100
 2 ms 592 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -