Submission #69505

#	Time	Username	Problem	Language	Result	Execution time	Memory
69505		E869120	철로 (IOI14_rail)	C++14	30 / 100	726 ms	99344 KiB

rail

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

int dist[5009][5009], lm[5009], ln[5009]; vector<int>x[5009];

int getDist(int p, int q) {
	if (p > q) swap(p, q);
	if (p == q) return 0;
	if (dist[p][q] != -1) return dist[p][q];
	
	int z = getDistance(p, q); dist[p][q] = z;
	return z;
}

int loc[5009], typ[5009];

void findLocation(int N, int first, int location[], int stype[]) {
	for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dist[i][j] = -1; }

	int minx = (1 << 30), a1 = 0;
	for (int i = 1; i < N; i++) { int r = getDist(0, i); if (r < minx) { minx = r; a1 = i; } }

	for (int i = 0; i < N; i++) {
		lm[i] = (1 << 30);
		for (int j = 0; j < N; j++) {
			if (i == j) continue;
			int r = getDist(i, j);
			if (r < lm[i]) { lm[i] = r; ln[i] = j; }
		}
		x[ln[i]].push_back(i);
	}
	vector<int>V; vector<pair<int, int>>W;
	for (int i = 0; i < N; i++) {
		if (x[i].size() >= 1) V.push_back(i);
	}
	for (int i = 0; i < V.size(); i++) {
		for (int j = i + 1; j < V.size(); j++) {
			if (ln[V[i]] == V[j] && ln[V[j]] == V[i]) W.push_back(make_pair(V[i], V[j]));
		}
	}
	for (int i = 0; i < W.size(); i++) {
		if (W[i].first != 0 && getDist(0, W[i].first) < getDist(a1, W[i].first)) {
			// 右にある
			if (getDist(W[i].first, 0) < getDist(W[i].second, 0)) swap(W[i].first, W[i].second);
			loc[W[i].second] = getDist(W[i].second, 0);
			loc[W[i].first] = loc[W[i].second] - getDist(W[i].first, W[i].second);
		}
		else {
			// 左にある
			if (W[i].second != a1 && getDist(W[i].first, a1) > getDist(W[i].second, a1)) swap(W[i].first, W[i].second);
			if (W[i].first == a1) swap(W[i].first, W[i].second);

			loc[W[i].first] = minx - getDist(W[i].first, a1);
			loc[W[i].second] = loc[W[i].first] + getDist(W[i].first, W[i].second);
		}
		typ[W[i].first] = 1;
		typ[W[i].second] = 2;
	}
	for (int i = 0; i < N; i++) {
		if (x[i].size() >= 1) continue;
		if (typ[ln[i]] == 2) {
			typ[i] = 1;
			loc[i] = loc[ln[i]] - getDist(i, ln[i]);
		}
		else {
			typ[i] = 2;
			loc[i] = loc[ln[i]] + getDist(ln[i], i);
		}
	}
	
	for (int i = 0; i < N; i++) location[i] = loc[i] + first;
	for (int i = 0; i < N; i++) stype[i] = typ[i];
	return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~
rail.cpp:39:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j < V.size(); j++) {
                       ~~^~~~~~~~~~
rail.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < W.size(); i++) {
                  ~~^~~~~~~~~~

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