Submission #245212

#	Time	Username	Problem	Language	Result	Execution time	Memory
245212		A02	Race (IOI11_race)	C++14	9 / 100	3080 ms	262148 KiB

race

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

using namespace std;

void root_tree (vector<long long> &parents, vector<vector<pair<int, long long> > > &adjacent, long long current){

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

        if (parents[child] == -1){
            parents[child] = current;
            root_tree(parents, adjacent, child);
        }
    }

}

void process_node(int N, vector<long long> &parents, vector<vector<pair<int, long long> > > &adjacent, vector<vector<long long> > &least_highways, long long current){


    least_highways[current][0] = 0;

    for (int i = 0; i < adjacent[current].size(); i++){
        long long child = adjacent[current][i].first;
        long long d = adjacent[current][i].second;

        if (parents[child] == current){

            if (least_highways[child][0] == N + 1){
                process_node(N, parents, adjacent, least_highways, child);
            }

            for (int r = d; r < least_highways[0].size(); r++){
                //cout << r << ' ' << d << ' ' << 'c' << child << ' ' << current << ' ' << least_highways[child][r - d] << endl;
                if (r - d >= 0){
                    least_highways[current][r] = min(least_highways[current][r], least_highways[child][r - d] + 1);
                }

            }
        }
    }


}

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;


    } else {

        vector<long long> parents (N, -1);
        parents[0] = -2;
        root_tree(parents, adjacent, 0);

        vector<vector<long long> > least_highways (N, vector<long long> (K + 1, N + 1));
        process_node(N, parents, adjacent, least_highways, 0);

        long long best = N + 1;

//        for (int i = 0; i < N; i ++){
//
//            cout << endl;
//            cout << i << ":" << endl;
//            for (int j = 0; j <= K; j++){
//                cout << least_highways[i][j] << ' ';
//            }
//            cout << endl;
//
//        }

        for (int n = 0; n < N; n++){

            for (int i = 0; i < adjacent[n].size(); i++){
                long long child1 = adjacent[n][i].first;
                if (parents[child1] == n){
                    for (int j = i + 1; j < adjacent[n].size(); j++){


                    long long child2 = adjacent[n][j].first;
                    if (parents[child2] == n){
                        long long added_distance = adjacent[n][i].second + adjacent[n][j].second;


                        for (int r = 0; r <= K - added_distance; r++){
                            best = min(best, 2 + least_highways[child1][r] + least_highways[child2][K - added_distance - r]);
                        }

                    }
                }


                }
                best = min (best, least_highways[n][K]);
                //cout << n << ' ' << best << endl;


        }

    }

    if (best > N){
        return -1;
    }

    return best;

    return N;
    }
}

Compilation message (stderr)

race.cpp: In function 'void root_tree(std::vector<long long int>&, std::vector<std::vector<std::pair<int, long long int> > >&, long long int)':
race.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adjacent[current].size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void process_node(int, std::vector<long long int>&, std::vector<std::vector<std::pair<int, long long int> > >&, std::vector<std::vector<long long int> >&, long long int)':
race.cpp:30:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adjacent[current].size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:40:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int r = d; r < least_highways[0].size(); r++){
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:91:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int r = 0; r < adjacent[current].size(); r++){
                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:135:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < adjacent[n].size(); i++){
                             ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:138:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = i + 1; j < adjacent[n].size(); j++){
                                         ~~^~~~~~~~~~~~~~~~~~~~

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