Submission #585666

#	Time	Username	Problem	Language	Result	Execution time	Memory
585666		LastRonin	Rail (IOI14_rail)	C++14	56 / 100	254 ms	72908 KiB

rail

#include "rail.h"
#include<bits/stdc++.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;
}


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

const int N = 5e3 + 100;

int cont = 0;
bool le[N];
int dist[N][N];
bool was[N][N];

int get(int a, int b) {
	if(was[a][b])return dist[a][b];
	cont++;
	return getDistance(a, b);
}

void findLocation(int n, int first, int location[], int stype[]) {
	location[0] = first;
	stype[0] = 1;
	for(int i = 1; i < n; i++) {
		dist[0][i] = get(0, i);
		was[0][i] = 1;				
	}
	int p = 0;
	while(1) {
		int mn = 1e9, z = 0;
		for(int i = 1; i < n; i++) {
			if(le[i] || stype[i])continue;
			if(mn > dist[0][i])
				mn = dist[0][i], z = i;
		}
		if(z == 0)break;
		location[z] = location[0] + dist[0][z];
		stype[z] = 2;
		if(!p) p = z;
		for(int i = 1; i < n; i++) {
			if(le[i] || stype[i])continue;
			dist[z][i] = get(z, i);
			was[z][i] = 1;
			if(dist[0][i] == dist[0][z] + dist[z][i]) {
				le[i] = 1;
				if(dist[z][i] < dist[0][z]) {
					location[i] = location[z] - dist[z][i];
					stype[i] = 1;
				}
			}
		}
	}
	assert(p != 0);
	while(1) {
		int mn = 1e9, z = 0;
		for(int i = 1; i < n; i++) {
			if(stype[i])continue;
			assert(was[p][i] == 1);
			if(mn > dist[p][i])
				mn = dist[p][i], z = i;
		}
		if(z == 0)break;
		location[z] = location[p] - dist[p][z];
		stype[z] = 1;
		for(int i = 1; i < n; i++) {
			if(stype[i])continue;
			dist[z][i] = get(z, i);
			was[z][i] = 1;
			if(dist[p][i] == dist[p][z] + dist[z][i]) {
				if(dist[z][i] < dist[p][z]) {
					location[i] = location[z] + dist[z][i];
					stype[i] = 2;
				}
			}
		}
	}
//	for(int i = 0; i < n; i++)
//		cout << stype[i] << " " << location[i] << "\n";

	assert(cont <= n * (n - 1)/2);
}
/*
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;
}
/*
3
6
1 3
2 4
1 1
2 2
1 5
2 6


*/

Compilation message (stderr)

rail.cpp:103:1: warning: "/*" within comment [-Wcomment]
  103 | /**/
      |  
rail.cpp:201:1: warning: "/*" within comment [-Wcomment]
  201 | /*
      |

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