Submission #1062939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062939		oscar1f	Rail (IOI14_rail)	C++17	56 / 100	317 ms	98900 KiB

rail

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

const int TAILLE_MAX=5000+5,INFINI=1000*1000*1000;
int nbBloc;
int dist[TAILLE_MAX][TAILLE_MAX];

void findLocation(int N, int first, int location[], int stype[]) {
    nbBloc=N;
    location[0]=first;
    stype[0]=1;
    if (N==1) {
        return ;
    }
    for (int i=0;i<nbBloc;i++) {
        for (int j=i+1;j<nbBloc;j++) {
            dist[i][j]=getDistance(i,j);
            dist[j][i]=dist[i][j];
        }
    }
    vector<pair<int,int>> somTri;
    vector<int> listeD;
    int pos,pb;
    for (int i=1;i<nbBloc;i++) {
        somTri.push_back({dist[0][i],i});
    }
    sort(somTri.begin(),somTri.end());
    for (auto i:somTri) {
        pos=i.second;
        pb=0;
        for (int j:listeD) {
            if (dist[0][pos]==dist[0][j]+dist[j][pos]) {
                pb=1;
            }
        }
        if (pb==0) {
            listeD.push_back(pos);
        }
    }

    int dernD=listeD.back();
    vector<int> listeC;
    location[dernD]=first+dist[0][dernD];
    stype[dernD]=2;
    somTri.clear();
    for (int i=0;i<nbBloc;i++) {
        if (i!=dernD) {
            somTri.push_back({dist[dernD][i],i});
        }
    }
    sort(somTri.begin(),somTri.end());
    for (auto i:somTri) {
        pos=i.second;
        pb=0;
        for (int j:listeC) {
            if (dist[dernD][pos]==dist[dernD][j]+dist[j][pos]) {
                pb=1;
            }
        }
        if (pb==0) {
            listeC.push_back(pos);
            location[pos]=location[dernD]-dist[dernD][pos];
            stype[pos]=1;
        }
    }

    int dernC=listeC.back();
    listeD.clear();
    somTri.clear();
    for (int i=0;i<nbBloc;i++) {
        if (i!=dernC) {
            somTri.push_back({dist[dernC][i],i});
        }
    }
    sort(somTri.begin(),somTri.end());
    for (auto i:somTri) {
        pos=i.second;
        pb=0;
        for (int j:listeD) {
            if (dist[dernC][pos]==dist[dernC][j]+dist[j][pos]) {
                pb=1;
            }
        }
        if (pb==0) {
            listeD.push_back(pos);
            location[pos]=location[dernC]+dist[dernC][pos];
            stype[pos]=2;
        }
    }
    return;
}

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