Submission #65327

#	Time	Username	Problem	Language	Result	Execution time	Memory
65327		theknife2001	Rail (IOI14_rail)	C++17	30 / 100	88 ms	916 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define ii pair < int , int >
#define se second
#define fi first


using namespace std;
const int N=5e3+55;
int dist[N];
ii a[N];


void findLocation(int n, int zero, int location[], int stype[])
{
    location[0]=zero;
    stype[0]=1;
    int temp;
    for(int i=1;i<n;i++)
    {
        temp=getDistance(0,i);
        a[i-1]={temp,i};
        dist[i]=temp;
    }
    sort(a,a+n-1);
    int first;
    int second;
    int last;
    int x,y;
    for(int i=0;i<n-1;i++)
    {
        if(!i)
        {
            first=a[i].se;
            last=first;
            location[first]=zero+a[i].fi;
            stype[first]=2;
            continue ;
        }
        x=getDistance(last,a[i].se);
        if(first!=last)
            y=getDistance(first,a[i].se);
        if(x+dist[last]==dist[a[i].se])
        {
            stype[a[i].se]=1;
            location[a[i].se]=location[last]-x;
        }
        else if(x==dist[a[i].se]+dist[last])
        {
            stype[a[i].se]=2;
            location[a[i].se]=zero+a[i].fi;

        }
        else if(a[i].fi+dist[first]==y)
        {
            second=a[i].se;
            stype[a[i].se]=1;
            location[a[i].se]=location[first]-y;
        }
        else
        {
            stype[a[i].se]=2;
            location[a[i].se]=location[second]+dist[a[i].se]-dist[second];
        }
    }
}

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