Submission #1170142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170142		onlk97	Rail (IOI14_rail)	C++20	30 / 100	32 ms	584 KiB

rail

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

void findLocation(int N,int first,int location[],int stype[]){
    for (int i=0; i<N; i++) stype[i]=0;
    location[0]=first; stype[0]=1;
    if (N==1) return;
    int dist0[N];
    for (int i=1; i<N; i++) dist0[i]=getDistance(0,i);
    int u=min_element(dist0+1,dist0+N)-dist0;
    location[u]=first+dist0[u]; stype[u]=2;
    int distu[N];
    for (int i=0; i<N; i++){
        if (i==u) continue;
        if (!i) distu[i]=dist0[u];
        else distu[i]=getDistance(u,i);
    }
    vector <pair <int,int> > vec;
    for (int i=1; i<N; i++){
        if (i!=u&&distu[i]<dist0[i]) vec.push_back({distu[i],i}); 
    }
    sort(vec.begin(),vec.end());
    int lst1=0;
    for (auto i:vec){
        if (i.first<=dist0[u]){
            location[i.second]=location[u]-i.first;
            stype[i.second]=1;
            continue;
        }
        int tp=getDistance(lst1,i.second);
        if (tp+distu[lst1]==i.first){
            location[i.second]=location[lst1]+tp;
            stype[i.second]=2;
        } else {
            location[i.second]=location[u]-i.first;
            stype[i.second]=1;
            lst1=i.second;
        }
    }
    vec.clear();
    for (int i=1; i<N; i++){
        if (i!=u&&distu[i]>dist0[i]) vec.push_back({dist0[i],i});
    }
    sort(vec.begin(),vec.end());
    int lst2=u;
    for (auto i:vec){
        int tp=getDistance(lst2,i.second);
        if (tp+dist0[lst2]==i.first){
            location[i.second]=location[lst2]-tp;
            stype[i.second]=1;
        } else {
            location[i.second]=location[0]+i.first;
            stype[i.second]=2;
            lst2=i.second;
        }
    }
}

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