Submission #1288692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288692		fenlynn	Rail (IOI14_rail)	C++20	0 / 100	59 ms	588 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
void findLocation(int N, int first, int location[], int stype[]){
    location[0]=first;
    stype[0]=1;
    if(N==1) return;
    vector<int> d0(N), d2(N);
    d0[0]=0;
    for(int i=1;i<N;i++) d0[i]=getDistance(0,i);
    int p2=-1, mn=INT_MAX;
    for(int i=1;i<N;i++) if(d0[i]<mn){ mn=d0[i]; p2=i; }
    location[p2]=first+mn;
    stype[p2]=2;
    d2[p2]=0;
    for(int i=0;i<N;i++) if(i!=p2) d2[i]=getDistance(p2,i);
    int delta = location[p2]-location[0];
    vector<int> V1,V2;
    for(int i=1;i<N;i++) if(i!=p2){
        if(d0[i]>d2[i]) V1.push_back(i); else V2.push_back(i);
    }
    while(!V1.empty()){
        int pt=-1, best=INT_MAX;
        for(int x:V1) if(d0[x]<best){ best=d0[x]; pt=x; }
        stype[pt]=2;
        location[pt]=location[0]+d0[pt];
        vector<int> nxt;
        for(int x:V1) if(x!=pt){
            int dd=getDistance(pt,x);
            if(d0[x]==d0[pt]+dd){ stype[x]=1; location[x]=location[0]+d0[pt]-dd; }
            else nxt.push_back(x);
        }
        V1.swap(nxt);
    }
    while(!V2.empty()){
        int pt=-1, best=INT_MAX;
        for(int x:V2) if(d2[x]<best){ best=d2[x]; pt=x; }
        stype[pt]=1;
        location[pt]=location[p2]-d2[pt];
        vector<int> nxt;
        for(int x:V2) if(x!=pt){
            int dd=getDistance(pt,x);
            if(d2[x]==d2[pt]+dd){ stype[x]=2; location[x]=location[p2]-d2[pt]+dd; }
            else nxt.push_back(x);
        }
        V2.swap(nxt);
    }
}

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