Submission #260718

#	Time	Username	Problem	Language	Result	Execution time	Memory
260718		A02	Rail (IOI14_rail)	C++14	56 / 100	1407 ms	98936 KiB

rail

#include "rail.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>

using namespace std;

vector<vector<int> > distances;

int gdistance(int i, int j){

    if (i == j){
        distances[i][i] = 0;
    }

    if (distances[i][j] == -1){
        distances[i][j] = getDistance(i, j);
        distances[j][i] = distances[i][j];
    }

    return distances[i][j];
}

int get_nearest(int s){

    int N = distances.size();
    vector<int> d (N, 0);

    for (int i = 0; i < N; i++){
        d[i] = gdistance(s, i);
    }

    d[s] = 2000001;

    int ds = distance(d.begin(), min_element(d.begin(), d.end()));
    return ds;
}

void findLocation(int N, int first, int location[], int stype[])
{

    distances = vector<vector<int> > (N, vector<int> (N, -1));

    for (int i = 0; i < N; i++){
        location[i] = -1;
        stype[i] = -1;
    }

    stype[0] = 1;
    location[0] = first;


    vector<int> d0 (N, -1);

    d0[0] = 0;

    for (int i = 1; i < N; i++){
        d0[i] = gdistance(0, i);
    }

    int x = distance(d0.begin(), min_element(++d0.begin(), d0.end()));

    location[x] = location[0] + d0[x];
    stype[x] = 2;

    vector<bool> is_leftx(N, false);

    is_leftx[x] = false;

    for (int i = 0; i < N; i++){
        if (i != 0 && i != x){
            if (gdistance(0, i) == gdistance(x, i) + gdistance(0, x)){
                is_leftx[i] = true;
            }
        }
    }

    is_leftx[0] = true;

    vector<pair<int, int> > left_stations;

    for (int i = 0; i < N; i++){
        if (is_leftx[i]){
            left_stations.push_back(make_pair(gdistance(i, x), i));
        }
    }

    sort(left_stations.begin(), left_stations.end());

    int currentC_front = left_stations[0].second;

    stype[currentC_front] = 1;
    location[currentC_front] = location[x] - gdistance(currentC_front, x);

    for (int i = 1; i < left_stations.size(); i++){

        int current_station = left_stations[i].second;
        int current_distance = left_stations[i].first;

        //cout << endl;
        //cout << " " << currentC_front << ' ' << current_station << ' ' << current_distance << endl;

        int nearest = get_nearest(current_station);
        //cout << 'n' << nearest << ' ' << stype[nearest] << endl;

        if (stype[nearest] == 1){
            location[current_station] = location[currentC_front] + gdistance(currentC_front, current_station);
            stype[current_station] = 2;
        } else {
            stype[current_station] = 1;
            location[current_station] = location[x] - gdistance(x, current_station);
            currentC_front = current_station;
        }

        //cout << current_station << ' ' << location[current_station] << ' ' << stype[current_station] << endl;
    }

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

    int y = get_nearest(x);

    vector<bool> is_righty(N, false);

    is_righty[y] = false;

    for (int i = 0; i < N; i++){
        if (i != x && i != y){
            if (gdistance(x, i) == gdistance(y, i) + gdistance(y, x)){
                is_righty[i] = true;
            }
        }
    }

    is_righty[x] = true;

    vector<pair<int, int> > right_stations;

    for (int i = 0; i < N; i++){
        if (is_righty[i]){
            right_stations.push_back(make_pair(gdistance(i, y), i));
        }
    }

    sort(right_stations.begin(), right_stations.end());

    int currentD_front = right_stations[0].second;

    stype[currentD_front] = 2;
    location[currentD_front] = location[y] + gdistance(currentD_front, y);
    //cout << y << endl;
    for (int i = 1; i < right_stations.size(); i++){

        int current_station = right_stations[i].second;
        int current_distance = right_stations[i].first;

        //cout << endl;
        //cout << " " << currentC_front << ' ' << current_station << ' ' << current_distance << endl;

        int nearest = get_nearest(current_station);
        //cout << 'n' << nearest << ' ' << stype[nearest] << endl;

        if (stype[nearest] == 2){
            location[current_station] = location[currentD_front] - gdistance(currentD_front, current_station);
            stype[current_station] = 1;
        } else {
            stype[current_station] = 2;
            location[current_station] = location[y] + gdistance(y, current_station);
            currentD_front = current_station;
        }

        //cout << current_station << ' ' << location[current_station] << ' ' << stype[current_station] << endl;
    }

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

}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < left_stations.size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~
rail.cpp:100:13: warning: unused variable 'current_distance' [-Wunused-variable]
         int current_distance = left_stations[i].first;
             ^~~~~~~~~~~~~~~~
rail.cpp:155:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < right_stations.size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~~
rail.cpp:158:13: warning: unused variable 'current_distance' [-Wunused-variable]
         int current_distance = right_stations[i].first;
             ^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44