Submission #260701

#	Time	Username	Problem	Language	Result	Execution time	Memory
260701		A02	Rail (IOI14_rail)	C++14	30 / 100	156 ms	98556 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];
}

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;

    for (int i = 0; i < N; i++){
        if (i != 0 && i != x){
            if (gdistance(0, i) == gdistance(x, i) + gdistance(0, x)){
                stype[i] = 1;
                location[i] = location[x] - gdistance(i, x);
            } else {
                stype[i] = 2;
                location[i] = location[0] + gdistance(0, i);
            }
            //cout << i << ' ' << location[i] << ' ' << stype[i] << endl;
        }
    }
}

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