Submission #1062980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062980		VMaksimoski008	Rail (IOI14_rail)	C++17	56 / 100	1684 ms	197252 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using Node = array<int, 3>;

int dist[5005][5005];

void findLocation(int N, int first, int location[], int stype[]) {
    stype[0] = 1; location[0] = first;
    
    for(int i=0; i<N; i++)
        for(int j=i+1; j<N; j++) dist[i][j] = dist[j][i] = getDistance(i, j);

    priority_queue<Node, vector<Node>, greater<Node> > pq;
    vector<bool> vis(N); vis[0] = 1;
    vector<int> D(N, 1e9); D[0] = 0;
    for(int i=1; i<N; i++) pq.push({ D[i] = dist[0][i], i, 0 });

    while(!pq.empty()) {
        auto [d, a, b] = pq.top(); pq.pop();
        if(vis[a]) continue;
        vis[a] = 1;

        stype[a] = 3 - stype[b];
        location[a] = location[b] + (stype[b] == 1 ? dist[a][b] : -dist[a][b]);

        for(int c=0; c<N; c++) {
            if(vis[c]) continue;
            if(D[c] > dist[a][c]) pq.push({ D[c] = dist[a][c], c, a });
        }
    }
}

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