Submission #1273453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273453		Aviansh	철로 (IOI14_rail)	C++20	8 / 100	75 ms	98380 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5005;

int mem[maxn][maxn];

int dist(int i, int j){
    if(mem[i][j]==-1){
        mem[i][j]=getDistance(i,j);
        mem[j][i]=mem[i][j];
    }
    return mem[i][j];
}

void findLocation(int n, int first, int location[], int stype[]) {
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            mem[i][j]=-1;
        }
    }
    location[0]=first;
    stype[0]=1;
    //base set
    array<int,2> dist0[n];
    dist0[0]={0,0};
    for(int i = 1;i<n;i++){
        dist0[i]={dist(0,i),i};
    }
    sort(dist0,dist0+n);
    int rig = dist0[1][1];
    int rigd = dist0[1][0];
    location[rig]=first+dist0[1][0];
    stype[rig]=2;
    int fir = rig;
    int fird = rigd;
    int lef = 0;
    assert(dist0[0][0]==0&&dist0[0][1]==0);
    int lefd = 0;
    for(int i = 2;i<n;i++){
        int dr = dist(rig,dist0[i][1]);
        int dl = dist(lef,dist0[i][1]);
        int d0 = dist(0,dist0[i][1]);
        if(d0<=dr+rigd){
            //means it is on the left
            int dlr = location[rig]-location[lef];
            if(dlr+dl==dr){
                //went to the right so not new left
                location[dist0[i][1]]=location[lef]+dl;
                stype[dist0[i][1]]=2;
            }
            else{
                location[dist0[i][1]]=location[rig]-dr;
                stype[dist0[i][1]]=1;
                lef=dist0[i][1];
                lefd=dist0[i][0];
            }
        }
        else{
            //means it is on right of right
            //so new right discovered
            rig=dist0[i][1];
            rigd=dist0[i][0];
            location[rig]=first+rigd;
            stype[rig]=2;
        }
    }
}

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