Submission #564814

#	Time	Username	Problem	Language	Result	Execution time	Memory
564814		hoanghq2004	Rail (IOI14_rail)	C++14	30 / 100	125 ms	98696 KiB

rail

/* This is sample grader for the contestant */
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
//
//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;
//}

const int N = 5010;
int d[N][N];

void findLocation(int n, int first, int location[], int stype[]) {
    memset(d, -1, sizeof(d));
    auto get = [&](int u, int v) {
        if (u == v) return 0;
        if (d[u][v] == -1) d[u][v] = getDistance(u, v);
        return d[u][v];
    };
    for (int i = 0; i < n; ++i) location[i] = -1;
    int R = 1;
    location[0] = first;
    stype[0] = 1;
    for (int i = 1; i < n; ++i)
        if (get(0, i) < get(0, R)) R = i;
    location[R] = first + get(0, R);
    stype[R] = 2;
    int L = 0;
    for (int i = 0; i < n; ++i)
        if (R != i && get(i, R) < get(L, R)) L = i;
    location[L] = location[R] - get(L, R);
    stype[L] = 1;
    for (int i = 0; i < n; ++i) {
        if (i == first || i == L || i == R) continue;
        if (get(L, i) == get(L, R) + get(R, i)) {
            location[i] = location[R] - get(R, i);
            stype[i] = 1;
        }
        if (get(R, i) == get(R, L) + get(L, i)) {
            location[i] = location[L] + get(L, i);
            stype[i] = 2;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (location[i] != -1) continue;
        int k = -1;
        for (int j = 0; j < n; ++j) {
            if (location[j] == -1) continue;
            if (k == -1 || get(i, j) < get(i, k)) k = j;
        }
        assert(k != -1);
        stype[i] = 3 - stype[k];
        if (stype[i] == 2) location[i] = location[k] + get(i, k);
        else location[i] = location[k] - get(i, k);
    }
}

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

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