Submission #557284

#	Time	Username	Problem	Language	Result	Execution time	Memory
557284		hibiki	Rail (IOI14_rail)	C++11	30 / 100	99 ms	54704 KiB

rail

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

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

// typedef struct Station {
//     int index;
//     int type;
//     int location;
//     int L,R;
// }STATION;
// long long cnt;
// static int S,SUBTASK;
// static STATION stations[10004];
//
// int cmp_fun_1(const void *a,const void *b)
// {
//     STATION c,d;
//     c = *(STATION*)(a);
//     d = *(STATION*)(b);
//     return c.location < d.location ? -1 : 1;
// }
//
// int cmp_fun_2(const void *a,const void *b)
// {
//     STATION c,d;
//     c = *(STATION*)(a);
//     d = *(STATION*)(b);
//     return c.index < d.index ? -1 : 1;
// }
//
// void now_I_want_to_getLR(){
//     int now = stations[S-1].index,i;
//     for(i=S-2;i>=0;i--){
//         stations[i].R = now;
//         if(stations[i].type==2)	now = stations[i].index;
//     }
//     now = stations[0].index;
//     for(i=1;i<S;i++){
//         stations[i].L = now;
//         if(stations[i].type==1)	now = stations[i].index;
//     }
// }
//
// int getDistance(int x,int y)
// {
//     cnt++;
//     if(x==y)	return 0;
//     if(x<0 || x>=S || y<0 || y>=S)    return -1;
//     if(stations[x].location > stations[y].location){
//         int tmp = x;
//         x = y;
//         y = tmp;
//     }
//     int ret = 0;
//     if(stations[x].type==1 && stations[y].type==1){
//         ret = stations[stations[y].R].location-stations[x].location+stations[stations[y].R].location-stations[y].location;
//     }else if(stations[x].type==1 && stations[y].type==2){
//         ret = stations[y].location-stations[x].location;
//     }else if(stations[x].type==2 && stations[y].type==2){
//         ret = stations[x].location-stations[stations[x].L].location+stations[y].location-stations[stations[x].L].location;
//     }else if(stations[x].type==2 && stations[y].type==1){
//         ret = stations[x].location-stations[stations[x].L].location+stations[stations[y].R].location
//         -stations[stations[x].L].location+stations[stations[y].R].location-stations[y].location;
//     }
//     return ret;
// }
//
//
// void getInput()
// {
//     int g;
//     g = scanf("%d",&SUBTASK);
//     g = scanf("%d",&S);
//     int s;
//     for (s = 0; s < S; s++) {
//         int type, location;
//         g = scanf(" %d %d",&type,&location);
//         stations[s].index = s;
//         stations[s].location = location;
//         stations[s].type = type;
//         stations[s].L = -1;
//         stations[s].R = -1;
//     }
//     qsort(stations, S, sizeof(STATION), cmp_fun_1);
//     now_I_want_to_getLR();
//     qsort(stations, S, sizeof(STATION), cmp_fun_2);
// }
//
// int serverGetStationNumber()
// {
//     return S;
// }
//
// int serverGetSubtaskNumber()
// {
//     return SUBTASK;
// }
//
// int serverGetFirstStationLocation()
// {
//     return stations[0].location;
// }

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 ;

    vec[0].clear();
    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 ;

    vec[nw_d].clear();
    for(int i=0;i<n;i++)
    {
        if(i==nw_d)continue;
        vec[nw_d].PB({fi_dis(nw_d,i),i});
        // printf("dis: %d %d: %d\n",nw_d,i,getDistance(nw_d,i));
    }
    sort(vec[nw_d].begin(),vec[nw_d].end());

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

    // printf("base: %d %d\n",base_c,base_d);
    // for(auto val:vec[nw_d])
    //     printf("%d %d\n",val.F,val.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;

    vec[base_c].clear();
    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]);
        // printf("i %d\n",i);
        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;

        // printf("go %d\n",go);

        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);

        // printf("%d\n",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]);

        // printf("%d\n",go);

        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;
        }
    }

    // for(int i=0;i<n;i++)
    // {
    //     printf("%d %d\n",location[i],stype[i]);
    // }

    return ;
}


// int main()
// {
//   int i;
//   getInput();
//   cnt = 0;
//
//   int location[10005];
//   int type[10005];
//   int ok = 1;
//   findLocation(S, serverGetFirstStationLocation(),location, type);
//   if(SUBTASK==3 && cnt>S*(S-1))	ok = 0;
//   if(SUBTASK==4 && cnt>3*(S-1))	ok = 0;
//
//
//   for (i = 0; i < S; i++)
//     if(type[i]!=stations[i].type || location[i]!=stations[i].location)
//       ok = 0;
//   if(ok==0)	printf("Incorrect");
//   else	printf("Correct");
//   return 0;
// }

Compilation message (stderr)

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

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