Submission #904738

#	Time	Username	Problem	Language	Result	Execution time	Memory
904738		StefanL2005	Race (IOI11_race)	C++14	21 / 100	3063 ms	18260 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define inf 1000*1000*1000

void DFS(int node, int parent, vector<vector<int>> &vecin, vector<vector<int>> &cost, vector<int> &dist, vector<int> &path)
{
    for (int i = 0; i < vecin[node].size(); i++)
    {
        auto V = vecin[node][i];

        if (V == parent)
            continue;

        path[V] = path[node] + 1;
        dist[V] = dist[node] + cost[node][i];
        DFS(V, node, vecin, cost, dist, path);
    }
}

int best_path(int n, int k, int H[][2], int L[])
{
    int best_ans = inf;
    vector<int> dist;
    vector<int> path;
    vector<vector<int>> vecin(n), cost(n);

    for (int i = 0; i < n-1; i++)
    {
        vecin[H[i][0]].push_back(H[i][1]);
        vecin[H[i][1]].push_back(H[i][0]);
        cost[H[i][0]].push_back(L[i]);
        cost[H[i][1]].push_back(L[i]);
    }

    for (int i = 0; i < n; i++)
    {
        dist = vector<int> (n);
        path = vector<int> (n);
        dist[i] = path[i] = 0;

        DFS(i, -1, vecin, cost, dist, path);

        for (int i = 0; i < n; i++)
            if (dist[i] == k)
                best_ans = min(best_ans, path[i]);
    }

    if (best_ans == inf)
        return -1;
    return best_ans;
}

Compilation message (stderr)

race.cpp: In function 'void DFS(int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
race.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < vecin[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~

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