Submission #426629

#	Time	Username	Problem	Language	Result	Execution time	Memory
426629		Dakto	Rail (IOI14_rail)	C++17	56 / 100	657 ms	99116 KiB

rail

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

using namespace std;

void findLocation(int n, int first, int location[], int stype[]) {
    location[0]=first;
    stype[0]=1;
    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;
    vector<bool> seen(n,0);
    seen[0]=1;
    vector<int> md(n,2000000);
    for(int i=1; i<n; i++) if(!seen[i]){
        int d=getDistance(0,i);
        if(d<md[i]){
            md[i]=d;
            q.emplace(d, make_pair(i,0));
        }
    }
    int left=n-1;
    while(!q.empty()){
        auto t=q.top();
        auto p=t.second;
        q.pop();
        if(seen[t.second.first]) continue;
        seen[t.second.first]=1;
        stype[p.first]=stype[p.second]==1?2:1;
        location[p.first]=location[p.second]+t.first*(stype[p.second]==1?1:-1);
        for(int i=1; i<n; i++) if(!seen[i]){
            int d=getDistance(p.first,i);
            if(d<md[i]){
                md[i]=d;
                q.emplace(d, make_pair(i,p.first));
            }
        }
        left--;
        if(!left) break;
    }
}

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