Submission #373947

#	Time	Username	Problem	Language	Result	Execution time	Memory
373947		urd05	Rail (IOI14_rail)	C++14	30 / 100	3093 ms	197768 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;

int n;
typedef pair<int,int> P;
typedef pair<P,int> Pi;
bool vis[5000];

void findLocation(int N, int first, int location[], int stype[]) {
    n=N;
    priority_queue<Pi,vector<Pi>,greater<Pi>> pq;
    location[0]=first;
    stype[0]=1;
    for(int i=1;i<N;i++) {
        int got=getDistance(0,i);
        pq.push(Pi(P(got,first+got),-i));
    }
    vis[0]=true;
    while (!pq.empty()) {
        Pi now=pq.top();
        pq.pop();
        int type=1;
        if (now.second<0) {
            type=2;
            now.second=-now.second;
        }
        if (vis[now.second]) {
            continue;
        }
        vis[now.second]=true;
        stype[now.second]=type;
        location[now.second]=now.first.second;
        for(int i=0;i<n;i++) {
            if (vis[i]) {
                continue;
            }
            int got=getDistance(now.second,i);
            pq.push(Pi(P(got,location[now.second]+got*(type==1?1:-1)),i*(type==1?-1:1)));
        }
    }
}

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