Submission #245199

#	Time	Username	Problem	Language	Result	Execution time	Memory
245199		A02	Race (IOI11_race)	C++14	21 / 100	56 ms	10232 KiB

race

#include "race.h"
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

int best_path(int N, int K, int H[][2], int L[])
{


    vector<vector<pair<int, long long> > > adjacent (N, vector<pair<int, long long> >());

        for (int i = 0; i < N - 1; i++){

            adjacent[H[i][0]].push_back(make_pair(H[i][1], L[i]));
            adjacent[H[i][1]].push_back(make_pair(H[i][0], L[i]));

        }


    if (N <= 1000){

        long long best = N + 1;

        for (int i = 0; i < N; i++){
            //cout << i << ' ' << endl;

            vector<pair<long long, long long> > distance (N, make_pair(-1, -1));
            queue<long long> to_visit;
            to_visit.push(i);

            distance[i].first = 0;
            distance[i].second = 0;

            while (!to_visit.empty()){


                long long current = to_visit.front();
                to_visit.pop();

                if (distance[current].second == K){
                    best = min(best, distance[current].first);
                }

                for (int r = 0; r < adjacent[current].size(); r++){
                    long long next = adjacent[current][r].first;

                    if (distance[next].first == -1){
                        distance[next].first = distance[current].first + 1;
                        distance[next].second = distance[current].second + adjacent[current][r].second;
                        to_visit.push(next);
                    }
                }

            }

        }

                    if (best == N + 1){
                return -1;
            }
            return best;


    }


    return N;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:50:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int r = 0; r < adjacent[current].size(); r++){
                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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