Submission #557362

#	Time	Username	Problem	Language	Result	Execution time	Memory
557362		hibiki	Rail (IOI14_rail)	C++11	100 / 100	109 ms	61260 KiB

rail

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

#define PB push_back
#define F first
#define S second

int n;
int dist[5050][5050];
set<int> C,D;

int fi_dis(int a,int b)
{
    if(a==b)return 0;
    if(dist[a][b])return dist[a][b];
    return dist[a][b]=dist[b][a]=getDistance(a,b);
}

void findLocation(int N, int first, int location[], int stype[])
{
    n=N;
    for(int i=0;i<n;i++)stype[i]=0;

    int a=0;
    location[a]=first;
    stype[a]=1;
    C.insert(first);

    if(n==1)return ;

    int mn=1e9,b=-1;
    for(int i=1;i<n;i++)
    {
        if(fi_dis(0,i)>mn)continue;

        mn=fi_dis(0,i);
        b=i;
    }

    location[b]=location[a]+mn;
    stype[b]=2;
    D.insert(location[b]);

    if(n==2)return ;

    for(int i=0;i<n;i++)
    {
        if(i==b)continue;
        fi_dis(b,i);

        if(fi_dis(b,i)<fi_dis(b,0)&&fi_dis(b,i)==fi_dis(a,i)-fi_dis(a,b))
        {
            location[i]=location[b]-fi_dis(b,i);
            stype[i]=1;
            C.insert(location[i]);
        }
    }

    vector<pair<int,int> > vec;
    for(int i=0;i<n;i++)
        vec.PB({fi_dis(a,i),i});
    sort(vec.begin(),vec.end());

    int d_right=b,c_left=a;
    for(int i=0;i<n;i++)
    {
        int nw=vec[i].S;

        if(stype[nw])continue;

        if(dist[a][nw]-dist[a][b]<dist[b][nw])
        {
            // right side
            // assume c type
            int dif=fi_dis(d_right,nw);
            int new_loca=location[d_right]-dif;
            int flip_loca=*D.upper_bound(new_loca);

            if(fi_dis(a,nw) == flip_loca - location[a] + flip_loca - new_loca)
            {
                // c type
                location[nw]=new_loca;
                stype[nw]=1;
                C.insert(location[nw]);
            }
            else
            {
                // d type
                location[nw]=location[a]+fi_dis(a,nw);
                stype[nw]=2;
                D.insert(location[nw]);
                d_right=nw;
            }
        }
        else
        {
            // left side
            // assume d type
            int dif=fi_dis(c_left,nw);
            int new_loca=location[c_left]+dif;
            int flip_loca=*prev(C.upper_bound(new_loca));

            if(fi_dis(b,nw) == location[b] - flip_loca + new_loca - flip_loca)
            {
                // type d
                location[nw]=new_loca;
                stype[nw]=2;
                D.insert(location[nw]);
            }
            else
            {
                // type c
                location[nw]=location[b]-fi_dis(b,nw);
                stype[nw]=1;
                C.insert(location[nw]);
                c_left=nw;
            }
        }
    }

    return ;
}

// int main()
// {
//     return 0;
// }

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