Submission #421833

#	Time	Username	Problem	Language	Result	Execution time	Memory
421833		Andyvanh1	Rail (IOI14_rail)	C++14	56 / 100	613 ms	98520 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
 
using namespace std;
 
#define vt vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,x) for(int (i) = 0; (i) < (x); (i)++)
#define INF 0x3f3f3f3f
#define MOD 1000000007
 
typedef long long ll;
typedef long double ld;
typedef vt<int> vi;
typedef pair<int,int> pii;
 
int dist[5003][5003];
 
void findLocation(int n,int first, int location[], int stype[]){
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            dist[i][j] = dist[j][i] = getDistance(i,j);
        }
    }
    location[0] = first;
    stype[0] = 1;
    int c = -1;
    int MinDist = INF;
    for(int i =1; i < n; i++){
        if(dist[0][i]<MinDist){
            MinDist = dist[0][i];
            c = i;
        }
    }
    location[c] = first+dist[0][c];
    stype[c] = 2;
    int b = -1;
    MinDist = INF;
 
    for(int i =0; i < n; i++){
        if(i==c)continue;
        if(dist[c][i]<MinDist){
            MinDist = dist[c][i];
            b = i;
        }
    }
    location[b] = location[c] - dist[c][b];
    stype[b] = 1;
 
 
    for(int i = 0; i < n; i++){
        if(i==c||i==b)continue;
        if(dist[b][i]-dist[c][i]==dist[b][c]){
            bool bol = false;
            int idex;
            for(int j = 0; j < n; j++){
                if(j==i||j==c||j==b)continue;
                if(dist[c][j]+dist[j][i] == dist[c][i]){
                    bol = true;
                    idex = j;
                    break;
                }
            }
            if(!bol){
                location[i] = location[c]-dist[c][i];
                stype[i] = 1;
            }else{
                location[i] = location[c] - dist[c][idex]+dist[idex][i];
                stype[i] = 2;
            }
 
 
        }else{
            bool bol = false;
            int idex;
            for(int j = 0; j < n; j++){
                if(j==b||j==c||j==i)continue;
                if(dist[b][j]+dist[j][i]==dist[b][i]){
                    bol = true;
                    idex = j;
                    break;
                }
 
            }
             if(!bol){
                    location[i] = location[b] + dist[b][i];
                    stype[i] = 2;
                }else{
                    location[i] = location[b] + dist[b][idex] - dist[idex][i];
                    stype[i] = 1;
                }
        }
    }
 
 
 
}

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