Submission #1080963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080963		DarkMatter	Rail (IOI14_rail)	C++14	56 / 100	1746 ms	197244 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[])
{
	location[0] = first, stype[0] = 1;
	vector<vector<int>>dis(N, vector<int>(N));
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++)
			dis[i][j] = dis[j][i] = getDistance(i, j);
	priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>>pq;
	vector<int>cost(N, 1e9 + 7);
	vector<bool>vis(N, false);
	cost[0] = 0, vis[0] = true;
	for (int i = 1; i < N; i++)
		cost[i] = dis[0][i], pq.push({ cost[i],{i,0} });
	while (!pq.empty()) {
		int curCost = pq.top().first, a = pq.top().second.first, b = pq.top().second.second;
		pq.pop();
		if (vis[a])
			continue;
		vis[a] = true;
		if (stype[b] == 1)
			location[a] = location[b] + dis[a][b], stype[a] = 2;
		else
			location[a] = location[b] - dis[a][b], stype[a] = 1;
		for (int i = 0; i < N; i++)
			if (!vis[i] && cost[i] > dis[a][i])
				cost[i] = dis[a][i], pq.push({ cost[i],{i,a} });
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:18:7: warning: unused variable 'curCost' [-Wunused-variable]
   18 |   int curCost = pq.top().first, a = pq.top().second.first, b = pq.top().second.second;
      |       ^~~~~~~

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