Submission #1081111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081111		DarkMatter	Rail (IOI14_rail)	C++14	56 / 100	1836 ms	198256 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, -1));
	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] = dis[i][0] = getDistance(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 (dis[a][b] == -1)
			dis[a][b] = dis[b][a] = getDistance(a, b);
		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 (dis[a][i] == -1)
				dis[a][i] = dis[i][a] = getDistance(a, 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:15:7: warning: unused variable 'curCost' [-Wunused-variable]
   15 |   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