Submission #12713

#	Time	Username	Problem	Language	Result	Execution time	Memory
12713		ainta	Rail (IOI14_rail)	C++98	100 / 100	126 ms	4684 KiB

rail

#include "rail.h"
#include<algorithm>
using namespace std;

#define MAX_M 1000010

int D1[5010], D2[5010];
int loc[5010];
int typ2[MAX_M];
int CL, CR;
struct AA{
	int dis, num;
	bool operator<(const AA &p)const{
		return dis < p.dis;
	}
}L[5010], R[5010];


void Add(int p, int a, int b){
	loc[p] = a;
	typ2[a] = b;
}

void Do(int p, int a, int d){
	if (typ2[loc[a]] == 1)Add(p, loc[a] + d, 2);
	else Add(p, loc[a] - d, 1);
}

void findLocation(int N, int first, int location[], int stype[])
{
	int i, MM = MAX_M, x, pv, d, t, k, j;
	Add(0, first, 1);
	for (i = 1; i < N; i++){
		D1[i] = getDistance(0, i);
		if (MM > D1[i]){
			MM = D1[i];
			x = i;
		}
	}
	Do(x, 0, D1[x]);
	for (i = 1; i < N; i++){
		if (i == x)continue;
		D2[i] = getDistance(x, i);
		if (D1[i] == D2[i] + D1[x]){
			if (D2[i] < D1[x]){
				Do(i, x, D2[i]);
			}
			else{
				L[CL].dis = D2[i], L[CL].num = i;
				CL++;
			}
		}
		else{
			R[CR].dis = D2[i], R[CR].num = i;
			CR++;
		}
	}
	sort(L, L + CL);
	sort(R, R + CR);
	pv = 0;
	for (i = 0; i < CL; i++){
		k = L[i].num;
		t = loc[x] - D2[k];
		d = getDistance(pv, k);
		if (d % 2 != (loc[pv] - t) % 2 || typ2[loc[pv] + (d - (loc[pv] - t)) / 2] == 1)Do(k, pv, d); 
		else{
			Do(k, x, D2[k]);
			pv = k;
		}
	}
	pv = x;
	for (i = 0; i < CR; i++){
		k = R[i].num;
		t = loc[0] + D1[k];
		d = getDistance(pv, k);
		if (d % 2 != (t - loc[pv]) % 2 || typ2[loc[pv] - (d - (t - loc[pv])) / 2] == 2)Do(k, pv, d);
		else{
			Do(k, 0, D1[k]);
			pv = k;
		}
	}
	for (i = 0; i < N; i++)location[i] = loc[i], stype[i] = typ2[loc[i]];
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:31:37: warning: unused variable 'j' [-Wunused-variable]
  int i, MM = MAX_M, x, pv, d, t, k, j;
                                     ^
rail.cpp:40:4: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Do(x, 0, D1[x]);
  ~~^~~~~~~~~~~~~

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