Submission #599021

#	Time	Username	Problem	Language	Result	Execution time	Memory
599021		snasibov05	Rail (IOI14_rail)	C++14	30 / 100	867 ms	262144 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<vector<int>> dist(n, vector<int>(n));
    for (int i = 0; i < n; ++i){
        for (int j = i+1; j < n; ++j) dist[i][j] = dist[j][i] = getDistance(i, j);
    }

    vector<set<pair<int, int>>> st(n);
    for (int i = 0; i < n; ++i){
        for (int j = 1; j < n; ++j) st[i].insert({dist[i][j], j});
    }

    vector<bool> found(n); found[0] = true;
    for (int i = 0; i < n-1; ++i){
        int mni = -1, mn = oo;
        for (int j = 0; j < n; ++j){
            if (!found[j]) continue;
            if (mni == -1 || st[j].begin()->first < mn) mni = j, mn = st[j].begin()->first;
        }

        assert(mni != -1);

        int to = st[mni].begin()->second;
        if (stype[mni] == 1){
            location[to] = location[mni] + mn;
            stype[to] = 2;
        } else{
            location[to] = location[mni] - mn;
            stype[to] = 1;
        }
        found[to] = true;

        for (int j = 0; j < n; ++j){
            st[j].erase({dist[j][to], to});
        }
    }

}

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