Submission #250981

#	Time	Username	Problem	Language	Result	Execution time	Memory
250981		A02	Dreaming (IOI13_dreaming)	C++14	47 / 100	1092 ms	29544 KiB

dreaming

#include "dreaming.h"
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <map>

using namespace std;

pair<long long, long long> calc_centre(int start, vector<vector<pair<long long, long long> > > &adjacent){


    queue<long long> to_visit;
    to_visit.push(start);

    map<long long, long long> distances1;
    distances1[start] = 0;

    long long longest_distance = 0;
    long long endpoint = start;

    while (!to_visit.empty()){

            long long current = to_visit.front();
            if (longest_distance < distances1[current]){
                longest_distance = distances1[current];
                endpoint = current;
            }

            to_visit.pop();

            for (int j = 0; j < adjacent[current].size(); j++){
                if (distances1.find(adjacent[current][j].first) == distances1.end()){
                    distances1[adjacent[current][j].first] = distances1[current] + adjacent[current][j].second;
                    to_visit.push(adjacent[current][j].first);
                }
            }
    }


    map<long long, long long> distances;
    map<long long, long long> parent;
    parent[endpoint] = endpoint;

    to_visit.push(endpoint);

    longest_distance = 0;
    long long startpoint = endpoint;

    while (!to_visit.empty()){

            long long current = to_visit.front();

            if (longest_distance < distances[current]){
                longest_distance = distances[current];
                startpoint = current;
            }

            to_visit.pop();

            for (long long j = 0; j < adjacent[current].size(); j++){
                if (distances.find(adjacent[current][j].first) == distances.end()){
                    distances[adjacent[current][j].first] = distances[current] + adjacent[current][j].second;
                    to_visit.push(adjacent[current][j].first);
                    parent[adjacent[current][j].first] = current;
                }
            }
    }

    long long radius = longest_distance;

    long long current = startpoint;

    long long left_distance = longest_distance;
    long long right_distance = 0;
    long long best = startpoint;

    while (current != endpoint){
        if(radius > max(left_distance, right_distance)){
            radius = max(left_distance, right_distance);
            best = current;
        }

        current = parent[current];
        left_distance = distances[current];
        right_distance = longest_distance - left_distance;

    }

    return make_pair(longest_distance, best);

}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

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

    for (int i = 0; i < M; i++){
        adjacent[A[i]].push_back(make_pair(B[i], T[i]));
        adjacent[B[i]].push_back(make_pair(A[i], T[i]));
    }

    vector<long long> region (N, -1);
    long long current_region = 0;
    vector<pair<long long, long long> > radii;

    for (int i = 0; i < N; i++){
        if (region[i] == -1){

            radii.push_back(calc_centre(i, adjacent));

            queue<long long> to_visit;
            to_visit.push(i);

            while (!to_visit.empty()){

                long long current = to_visit.front();
                to_visit.pop();
                region[current] = current_region;

                for (long long j = 0; j < adjacent[current].size(); j++){
                    if (region[adjacent[current][j].first] == -1){
                        to_visit.push(adjacent[current][j].first);
                    }
                }

            }


            current_region++;
        }

    }

    while (radii.size() > 1){

        pair<long long, long long > a1 = radii[radii.size() - 1];
        pair<long long, long long > a2 = radii[radii.size() - 2];
        radii.pop_back();
        radii.pop_back();

        long long x = a1.second;
        long long y = a2.second;
        adjacent[x].push_back(make_pair(y, L));
        adjacent[y].push_back(make_pair(x, L));
        //cout << x << ' ' << y << endl;
        radii.push_back(calc_centre(x, adjacent));


    }


    return radii[0].first;
}

Compilation message (stderr)

dreaming.cpp: In function 'std::pair<long long int, long long int> calc_centre(int, std::vector<std::vector<std::pair<long long int, long long int> > >&)':
dreaming.cpp:33:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < adjacent[current].size(); j++){
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:62:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (long long j = 0; j < adjacent[current].size(); j++){
                                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:122:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (long long j = 0; j < adjacent[current].size(); j++){
                                       ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23