Submission #638617

#	Time	Username	Problem	Language	Result	Execution time	Memory
638617		ggoh	Rail (IOI14_rail)	C++14	100 / 100	100 ms	48684 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef pair<int,int> pii;

int dis[5005][5005],minind,ind[2000002];
void findLocation(int n, int first, int location[], int stype[])
{
    location[0]=first;
    stype[0]=1;
    if(n==1)return ;

    for(int i=1;i<n;i++)
    {
        dis[0][i]=dis[i][0]=getDistance(0,i);
        if(!minind || dis[0][minind]>dis[0][i])minind=i;
    }
    int c0,d0;
    d0=minind;
    location[d0]=location[0]+dis[0][d0];
    stype[d0]=2;
    minind=d0;
    for(int i=0;i<n;i++)
    {
        if(i==d0)continue;
        dis[d0][i]=dis[i][d0]=getDistance(d0,i);
        if(minind==d0 || dis[d0][minind]>dis[d0][i])minind=i;
    }
    c0=minind;
    location[c0]=location[d0]-dis[d0][c0];
    stype[c0]=1;
    for(int i=0;i<n;i++)
    {
        if(i==0 || i==c0 || i==d0)continue;
        dis[c0][i]=dis[0][i]-(dis[0][d0]-dis[c0][d0]);
    }
    vector<pii>ri,le;
    for(int i=0;i<n;i++)
    {
        if(i==c0 || i==d0)continue;
        if(dis[c0][i]<dis[d0][i])ri.push_back({dis[c0][i],i});
        else le.push_back({dis[d0][i],i});
    }
    sort(ri.begin(),ri.end());
    sort(le.begin(),le.end());
    //right
    int sum;
    vector<pii>D;
    memset(ind,-1,sizeof(ind));
    sum=location[d0]-location[c0];
    D.push_back({sum,d0});
    ind[sum]=sz(D)-1;
    for(auto &x:ri)
    {
        int dis=x.first;
        int i=x.second;
        int j=sz(D)-1;
        int ch=0;
        int dis2=getDistance(D[j].second,i);
        if((sum+dis-dis2)%2==0 && sum+dis-dis2>0 && ind[(sum+dis-dis2)/2]!=-1)
        {
          int k=ind[(sum+dis-dis2)/2];
          if(k>0 && D[k].first-D[k-1].first>dis2-sum+D[k].first)
          {
            ch=1;
            location[i]=location[D[k].second]-dis2+sum-D[k].first;
            stype[i]=1;
          }
        }
        if(ch==0)
        {
            location[i]=location[c0]+dis;
            stype[i]=2;
            sum=location[i]-location[c0];
            D.push_back({sum,i});
            ind[sum]=sz(D)-1;
        }
    }
    
    //left
    sum=0;
    vector<pii>C;
    memset(ind,-1,sizeof(ind));
    sum=location[d0]-location[c0];
    C.push_back({sum,c0});
    ind[sum]=sz(C)-1;
    for(auto &x:le)
    {
        int dis=x.first;
        int i=x.second;
        int j=sz(C)-1;
        int ch=0;
        int dis2=getDistance(C[j].second,i);
        if((sum+dis-dis2)%2==0 && sum+dis-dis2>0 && ind[(sum+dis-dis2)/2]!=-1)
        {
          int k=ind[(sum+dis-dis2)/2];
          if(k>0 && C[k].first-C[k-1].first>dis2-sum+C[k].first)
          {
            ch=1;
            location[i]=location[C[k].second]+dis2-sum+C[k].first;
            stype[i]=2;
          }
        }
        if(ch==0)
        {
            location[i]=location[d0]-dis;
            stype[i]=1;
            sum=location[d0]-location[i];
            C.push_back({sum,i});
            ind[sum]=sz(C)-1;
        }
    }

    return ;
}

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