Submission #557262

#	Time	Username	Problem	Language	Result	Execution time	Memory
557262		hibiki	Rail (IOI14_rail)	C++11	0 / 100	107 ms	57916 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];
int nw_c,nw_d,base_c,base_d;
bool done[5050];
vector<int> l,r;
vector<pair<int,int> > vec[5050];

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[])
{
    // memset(dist,0,sizeof(dist));
    // memset(done,0,sizeof(done));
    // l.clear();
    // r.clear();
    // for(int i=0;i<5050;i++)
    //     vec[i].clear();
    n=N;

    nw_c=0;
    location[0]=first;
    stype[0]=1;
    done[0]=true;

    if(n==1)return ;

    for(int i=1;i<n;i++)
        vec[0].PB({fi_dis(0,i),i});
    sort(vec[0].begin(),vec[0].end());

    nw_d=vec[nw_c][0].S;
    location[nw_d]=location[nw_c]+vec[nw_c][0].F;
    stype[nw_d]=2;
    done[nw_d]=true;

    if(n==2)return ;

    for(int i=0;i<n;i++)
    {
        if(i==nw_d)continue;
        vec[nw_d].PB({fi_dis(nw_d,i),i});
    }
    sort(vec[nw_d].begin(),vec[nw_d].end());

    base_d=nw_d;
    base_c=vec[nw_d][0].S;

    nw_c=vec[nw_d][0].S;
    location[nw_c]=location[nw_d]-vec[nw_d][0].F;
    stype[nw_c]=1;
    done[nw_c]=true;

    for(int i=0;i<n;i++)
    {
        int a=base_c,b=i;
        if(a==b)continue;
        dist[a][b]=dist[b][a]=dist[0][i]-(location[a]-location[0]);
        vec[a].PB({dist[a][b],i});
    }
    sort(vec[base_c].begin(),vec[base_c].end());

    for(int i=0;i<vec[base_c].size();i++)
    {
        int go=vec[base_c][i].S;

        if(done[go])continue;

        if(dist[base_c][go]<dist[base_d][go]) r.PB(go);
        else l.PB(go);
    }

    nw_c=base_c;
    nw_d=base_d;
    for(int i=0;i<r.size();i++)
    {
        int go=r[i];
        int nw_c_go=dist[base_c][go]-(location[nw_c]-location[base_c]);
        int nw_d_go=fi_dis(nw_d,go);

        done[go]=true;
        if(nw_c_go<nw_d_go)
        {
            // type d
            location[go]=location[nw_c]+nw_c_go;
            stype[go]=2;
            nw_d=go;
        }
        else
        {
            // type c
            location[go]=location[nw_d]-nw_d_go;
            stype[go]=1;
            if(location[nw_c]<location[go])
                nw_c=go;
        }
    }

    nw_c=base_c;
    nw_d=base_d;
    for(int i=0;i<l.size();i++)
    {
        int go=l[i];
        int nw_c_go=fi_dis(nw_c,go);
        int nw_d_go=dist[base_d][go]-(location[base_d]-location[nw_d]);

        done[go]=true;
        if(nw_d_go<nw_c_go)
        {
            // type c
            location[go]=location[nw_d]-nw_d_go;
            stype[go]=1;
            nw_c=go;
        }
        else
        {
            // type d
            location[go]=location[nw_c]+nw_c_go;
            stype[go]=2;
            if(location[go]<location[nw_d])
                nw_d=go;
        }
    }

    return ;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<vec[base_c].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
rail.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<r.size();i++)
      |                 ~^~~~~~~~~
rail.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(int i=0;i<l.size();i++)
      |                 ~^~~~~~~~~

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