Submission #612451

#	Time	Username	Problem	Language	Result	Execution time	Memory
612451		snasibov05	Rail (IOI14_rail)	C++14	8 / 100	122 ms	516 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

#define oo 1000000000

void findLocation(int n, int first, int location[], int stype[]){
    location[0] = first;
    stype[0] = 1;

    vector<int> d0(n);
    for (int i = 1; i < n; ++i) d0[i] = getDistance(0, i);
    vector<bool> visited(n); visited[0] = true;

    if (n == 1) return;

    int mni = -1;
    for (int i = 0; i < n; ++i){
        if (!visited[i] && (mni == -1 || d0[i] < d0[mni])) mni = i;
    }
    location[mni] = location[0] + d0[mni];
    stype[mni] = 2;
    visited[mni] = true;

    int l = 0, r = mni;
    for (int j = 2; j < n; ++j){
        mni = -1;
        for (int i = 0; i < n; ++i){
            if (!visited[i] && (mni == -1 || d0[i] < d0[mni])) mni = i;
        }

        int dl = getDistance(l, mni), dr = getDistance(r, mni);
        visited[mni] = true;
        if (l != 0 && d0[mni] == dl + d0[l]) {
            location[mni] = location[l] + dl;
            stype[mni] = 2;
        } else if (d0[mni] == dr + d0[r]){
            location[mni] = location[r] - dr;
            stype[mni] = 1;
            if (location[mni] < location[l]) l = mni;
        } else{
            location[mni] = location[0] + d0[mni];
            stype[mni] = 2;
            r = mni;
        }
    }

}

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