Submission #1139343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139343		Aliyyiakbar	Race (IOI11_race)	C++20	0 / 100	0 ms	320 KiB

race

#include "race.h"
#include "bits/stdc++.h"
using namespace std;


int res = 1e9;
void dfs(vector<vector< pair<int, int> >> &v, int node, int par, int depth, int total, int target)
{
    if ((int)v[node].size() == 1 && par != -1)
    {
        if (total == target)
        {
            res = min(res, depth - 1);
        }
        return;
    }
    if (total > target)
    {
        return;
    }
    if (total == target)
    {
        res = min(res, depth - 1);
        return;
    }
    for (auto &to : v[node])
    {
        if (par != to.first)
        {
            dfs(v, to.first, node, depth + 1, total + to.second, target);
        }
    }
}

int best_path(int n, int k, int h[][2], int l[])
{
    vector<vector< pair<int, int> >> v(n + 1, vector< pair<int, int> >(0));
    for (int i = 0; i < n; ++i)
    {
        v[h[i][0] + 1].push_back({h[i][1] + 1, l[i]});
        v[h[i][1] + 1].push_back({h[i][0] + 1, l[i]});
    }
    for (int i = 1; i <= n; ++i)
    {
        dfs(v, i, -1, 1, 1, k);
    }
    return (res == 1e9 ? -1 : res);
}

/*
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3 4 5 4 6 3 2 5 6 7
2
*/

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