Submission #65375

#	Time	Username	Problem	Language	Result	Execution time	Memory
65375		theknife2001	Rail (IOI14_rail)	C++17	30 / 100	887 ms	99848 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][N];
ii a[N];
vector < int > vec;


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[0][i]=temp;
        dist[i][0]=temp;
    }
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            dist[i][j]=dist[j][i]=getDistance(i,j);
        }
    }
    sort(a,a+n-1);
    int first;
    int second=-1;
    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=dist[last][a[i].se];
//        if(first!=last)
//            y=getDistance(first,a[i].se);
        bool k=0;
        for(auto se:vec)
        {
            k|=(dist[se][a[i].se]+dist[first][a[i].se]==a[i].fi);
        }
//        cout<<a[i].se<<' '<<a[i].fi<<' '<<dist[0][first]<<' '<<x<<' '<<dist[first][a[i].se]<<' '<<k<<endl;
        if(x+dist[0][last]==a[i].fi&&!k)
        {
            if(last==first)
                if(dist[0][last]<x)
                        vec.push_back(a[i].se);
            stype[a[i].se]=1;
            location[a[i].se]=location[last]-x;
        }
        else if(x==a[i].fi+dist[0][last])
        {
            last=a[i].se;
            stype[a[i].se]=2;
            location[a[i].se]=zero+a[i].fi;

        }
        else
        {
            if(vec.size()!=0)
            {
                k=0;
                for(auto se:vec)
                {
                    if(dist[a[i].se][se]+dist[first][a[i].se]==a[i].fi)
                    {
                        stype[a[i].se]=2;
                        location[a[i].se]=location[second]+dist[se][a[i].se];
                        k=1;
                        break;
                    }
                }
            }
            if(k)
                continue ;
            vec.push_back(a[i].se);
            stype[a[i].se]=1;
            location[a[i].se]=zero-a[i].fi+2*dist[0][first];
        }
    }
//    cout<<endl;
//    for(int i=0;i<n;i++)
//        cout<<stype[i]<<' '<<location[i]<<endl;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:36:9: warning: unused variable 'second' [-Wunused-variable]
     int second=-1;
         ^~~~~~
rail.cpp:38:11: warning: unused variable 'y' [-Wunused-variable]
     int x,y;
           ^

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