제출 #585591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585591		SeDunion	철로 (IOI14_rail)	C++17	56 / 100	2093 ms	99848 KiB

rail

#include "rail.h"
#include<iostream>
#include<set>

using namespace std;

const int N = 5055;
const int inf = 1e9;

int d[N][N];

int q[N];

int n;

int used[N];

void findLocation(int N, int first, int location[], int stype[]) {
	n = N;
	for (int i = 0 ; i < n ; ++ i) {
		for (int j = 0 ; j < i ; ++ j) {
			d[i][j] = d[j][i] = getDistance(i, j);
		}
	}
	for (int i = 0 ; i < n ; ++ i) {
		q[i] = inf;
	}
	q[0] = 0;
	set<pair<int,int>>st;
	st.insert({0, 0});
	stype[0] = 1;
	location[0] = first;
	while (st.size()) {
		int v = st.begin()->second;
		st.erase(st.begin());
		used[v] = 1;
		for (int i = 0 ; i < n ; ++ i) {
			if (used[i]) continue;
			if (q[i] > d[i][v]) {
				st.erase({q[i], i});
				q[i] = d[i][v];
				stype[i] = 3 - stype[v];
				if (stype[v] == 1) location[i] = location[v] + d[i][v];
				else location[i] = location[v] - d[i][v];
				st.insert({q[i], i});
			}
		}
	}
}

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