Submission #1306676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306676		nicolo_010	철로 (IOI14_rail)	C++20	30 / 100	32 ms	592 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

void findLocation(int n, int first, int location[], int stype[]) {
	for (int i=0; i<n; i++) {
		location[i] = -1;
	}
	location[0] = first;
	if (n==1) {
		return;	
	}
	stype[0] = 1;
	int c;
	vector<int> dis(n);
	dis[0] = 0;
	for (int i=1; i<n; i++) {
		dis[i] = getDistance(0, i);
	}
	int mn=1e9;
	for (int i=1; i<n; i++) {
		if (dis[i] < mn) {
			c = i;
			mn = dis[i];
		}
	}
	vector<int> disc(n);
	disc[c] = 0;
	for (int i=0; i<n; i++) {
		disc[i] = getDistance(i, c);
	}
	stype[c] = 2;
	location[c] = location[0] + dis[c];
	for (int i=0; i<n; i++) {
		if (i==0 || i==c) continue;
		if (dis[i] != dis[c]+disc[i] || disc[i] > location[c]) continue;
		if (dis[i] == dis[c]+disc[i]) {
			stype[i] = 1;
			location[i] = location[c]-disc[i];
		}
		else {
			continue;
		}
	}
	int left=0;
	mn = location[0];
	for (int i=0; i<n; i++) {
		//cout << i << " " << location[i] << endl;
		if (location[i] >= 0 && location[i] < mn && stype[i]==1) {
			mn = location[i];
			left = i;
		}
	}
	for (int i=0; i<n; i++) {
		if (location[i] <= -1) {
			int dist = getDistance(left, i);	
			//cout << location[left] << " " << dist << endl;
			location[i] = location[left] + dist;
			stype[i] = 2;
		}
	}
}

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