Submission #113970

#	Time	Username	Problem	Language	Result	Execution time	Memory
113970		E869120	Rail (IOI14_rail)	C++14	100 / 100	155 ms	32116 KiB

rail

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

int N, minx = 10000000, minid, A[100009], T[100009], dp[5009][5009];
vector<pair<int, int>> vec1, vec2;

int getDist(int u, int v) {
	if (u == v) return 0;
	if (u > v) swap(u, v);
	if (dp[u][v] >= 1) return dp[u][v];
	
	int E = getDistance(u, v);
	dp[u][v] = E;
	return E;
}

void solve_1() {
	int pos = 0; vector<int> E; E.push_back(0);
	for (int i = 0; i < vec1.size(); i++) {
		if (vec1[i].first < minx) {
			T[vec1[i].second] = 1;
			A[vec1[i].second] = A[minid] - vec1[i].first;
		}
		else {
			int Z1 = getDist(minid, vec1[i].second);
			int Z2 = getDist(minid, pos);
			int Z3 = getDist(pos, vec1[i].second);
			
			int Z = A[pos] + Z3;
			for (int j = 0; j < E.size(); j++) {
				if (abs(A[minid] - A[E[j]]) + abs(A[E[j]] - Z) == Z1) {
					A[vec1[i].second] = Z;
					T[vec1[i].second] = 2;
					break;
				}
			}
			if (T[vec1[i].second] == 0) {
				A[vec1[i].second] = A[minid] - Z1;
				T[vec1[i].second] = 1;
				pos = vec1[i].second;
				E.push_back(vec1[i].second);
			}
		}
	}
}

void solve_2() {
	int pos = minid; vector<int> E; E.push_back(minid);
	for (int i = 0; i < vec2.size(); i++) {
		int Z1 = getDist(0, vec2[i].second);
		int Z2 = getDist(0, pos);
		int Z3 = getDist(pos, vec2[i].second);
		
		int Z = A[pos] - Z3;
		for (int j = 0; j < E.size(); j++) {
			if (abs(A[0] - A[E[j]]) + abs(A[E[j]] - Z) == Z1) {
				A[vec2[i].second] = Z;
				T[vec2[i].second] = 1;
				break;
			}
		}
		if (T[vec2[i].second] == 0) {
			A[vec2[i].second] = A[0] + Z1;
			T[vec2[i].second] = 2;
			pos = vec2[i].second;
			E.push_back(vec2[i].second);
		}
	}
}

void findLocation(int n, int first, int location[], int stype[]) {
	N = n; A[0] = first; T[0] = 1;
	
	for (int i = 1; i < N; i++) {
		int E = getDist(0, i);
		if (minx > E) { minx = E; minid = i; }
	}
	A[minid] = A[0] + minx; T[minid] = 2;
	
	int minv = 10000000; for (int i = 0; i < N; i++) { if (i == minid) continue; minv = min(minv, getDist(minid, i)); }
	
	for (int i = 0; i < N; i++) {
		if (i == 0 || i == minid) continue;
		int V1 = getDist(0, i) - (minx - minv);
		int V2 = getDist(minid, i);
		if (V1 > V2) vec1.push_back(make_pair(V2, i));
		else vec2.push_back(make_pair(V1 + (minx - minv), i));
	}
	sort(vec1.begin(), vec1.end());
	sort(vec2.begin(), vec2.end());
	
	//cout << endl;
	//cout << "Base value:" << endl;
	//cout << minx << " " << minid << endl;
	//cout << endl;
	//cout << "Value of vec1:" << endl;
	//for (int i = 0; i < vec1.size(); i++) cout << "(" << vec1[i].first << ", " << vec1[i].second << ")" << endl;
	//cout << endl;
	//cout << "Value of vec2:" << endl;
	//for (int i = 0; i < vec2.size(); i++) cout << "(" << vec2[i].first << ", " << vec2[i].second << ")" << endl;
	//cout << endl;
	
	solve_1();
	solve_2();
	
	for (int i = 0; i < N; i++) {
		//cout << "(" << A[i] << ", " << T[i] << ")" << endl;
		location[i] = A[i]; stype[i] = T[i];
	}
}

Compilation message (stderr)

rail.cpp: In function 'void solve_1()':
rail.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec1.size(); i++) {
                  ~~^~~~~~~~~~~~~
rail.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < E.size(); j++) {
                    ~~^~~~~~~~~~
rail.cpp:27:8: warning: unused variable 'Z2' [-Wunused-variable]
    int Z2 = getDist(minid, pos);
        ^~
rail.cpp: In function 'void solve_2()':
rail.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec2.size(); i++) {
                  ~~^~~~~~~~~~~~~
rail.cpp:56:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < E.size(); j++) {
                   ~~^~~~~~~~~~
rail.cpp:52:7: warning: unused variable 'Z2' [-Wunused-variable]
   int Z2 = getDist(0, pos);
       ^~

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