Submission #561158

#	Time	Username	Problem	Language	Result	Execution time	Memory
561158		proma	Race (IOI11_race)	C++17	9 / 100	394 ms	48968 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;
const int INF = 1e9;

vector <pair <int, int>> g[N];
int ans, k, used[N], dp[N][105];

void dfs(int v) {
    used[v] = 1;
    for (int i = 1; i <= k; i ++) dp[v][i] = INF;
    for (auto i: g[v]) {
        if (!used[i.first]) {
            dfs(i.first);
            for (int j = 1; j <= k; j ++) {
                if (j - i.second >= 0) {
                    dp[v][j] = min(dp[v][j], dp[i.first][j-i.second] + 1);
                }
            }
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for (int i = 0; i < N; i ++) {
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    int ans = INF;
    vector <int> nodes = {0, N/6, N/5, N/4, N/3, N/2, N-1};
    for (auto v: nodes) {
        memset(used, 0, sizeof(used));
        dfs(v);
        for (int i = 0; i < N; i ++) {
            ans = min(ans, dp[i][k]);
        }
    }
    if (ans == INF) ans = -1;
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57