Submission #690893

#	Time	Username	Problem	Language	Result	Execution time	Memory
690893		Khizri	Rail (IOI14_rail)	C++17	30 / 100	67 ms	504 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=5000+5;
int dp[mxn][mxn],color[mxn];
int ask(int i,int j){
    if(i==j) return 0;
    if(dp[i][j]) return dp[i][j];
    return dp[i][j]=getDistance(i,j);
}
void findLocation(int n, int first, int location[], int stype[])
{
    int mx=1e5,idx=0;
    for(int i=1;i<n;i++){
        if(ask(0,i)<mx){
            mx=ask(0,i);
            idx=i;
        }
    }
    location[idx]=first+mx;
    location[0]=first;
    stype[idx]=2;
    stype[0]=1;
    color[0]=1;
    color[idx]=1;
    for(int i=1;i<n;i++){
        if(color[i]) continue;
        int say=ask(0,i);
        if(ask(0,i)==ask(0,idx)+ask(idx,i)){
            location[i]=location[idx]-ask(idx,i);
            stype[i]=1;
        }
        else{
            location[i]=first+say;
            stype[i]=2;
        }
    }
}

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