Submission #794453

#	Time	Username	Problem	Language	Result	Execution time	Memory
794453		medmdg	Rail (IOI14_rail)	C++14	30 / 100	48 ms	856 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using ll =long long;
ll LINF=1000000000000000000;
int INF=1000000000;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>

using namespace std;

void findLocation(int n, int first, int location[], int stype[]){
    for(int i=0;i<n;i++){
        location[i]=0;
        stype[i]=0;
    }
    int second;
    location[0]=first;
    multimap<int,int>df;
    vi distf(n);
    vi dists(n);
    for(int i =1;i<n;i++){
        int dist=getDistance(i,0);
        df.insert(make_pair(dist,i));
        distf[i]=dist;
    }
    second=df.begin()->second;

    for(int i=1;i<n;i++){
        if(i==second)continue;
        int dist=getDistance(i,second);
        dists[i]=dist;
    }
    location[second]=first+distf[second];
    dists[0]=distf[second];
    stype[0]=1;
    stype[second]=2;
    for(int i=0;i<n;i++){
        if(i==0 || i==second)continue;
        if(dists[i]<distf[second] && distf[i]==dists[i]+ distf[second] ){
            stype[i]=1;
            location[i]=location[second]-dists[i];
        }
    }
    multimap<int,int>left;
    multimap<int,int>right;

    for(int i=0;i<n;i++){
        if(stype[i] )continue;
        if(distf[i]==distf[second]+dists[i])left.insert(make_pair(dists[i],i));
        else right.insert(make_pair(distf[i],i));
    }
    int last=second;
    for(auto & itr : right){
        int dist= getDistance(itr.second,last);
        if(distf[itr.second]==distf[last]+dist){
            location[itr.second]=location[last]-dist;
            stype[itr.second]=1;
        }
        else{
            location[itr.second]=first+distf[itr.second];
            stype[itr.second]=2;
            last=itr.second;
        }
    }
    last=0;
    for(auto itr=left.begin();itr!=left.end();itr++){
        int dist= getDistance(itr->second,last);
        if(dists[itr->second]==dists[last]+dist){
            location[itr->second]=location[last]+dist;
            stype[itr->second]=2;
        }
        else{
            location[itr->second]= location[second]-dists[itr->second];
            stype[itr->second]=1;
            last=itr->second;
        }
    }


}

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