Submission #511698

#	Time	Username	Problem	Language	Result	Execution time	Memory
511698		Tizariox	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	1147 ms	59392 KiB

crocodile

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

using ll = long long;
using pii = pair<int, int>;

#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define F0R1(i, a) for (int i = 1; i <= (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define F0Rd1(i, a) for (int i = a; i > 0; i--)
#define SORT(vec) sort(vec.begin(), vec.end())
#define S0RT(arr, n) sort(arr, arr + n)

#define pA first
#define pB second
#define MOD 1000000007
#define nl "\n"
#define pb push_back

int n, m, k;
vector<int> exits;
int pathInd = 0; // index each path to make sure we don't duplicate paths

class cmp {
  public:
	bool operator()(vector<int> a, vector<int> b) { 
		if (a[1] == b[1]) {
			return a[2] > b[2];
		}
		return a[1] > b[1]; 
	}
};

pair<pii, pii> dist[100000]; // 2 smallest distances to each node
vector<pii> adj[100000];
int shortestVis[100000]; // whether the shortest path for each node has already been taken

void dijkstra() { // traceback
	for (int i = 0; i < n; i++) {
		dist[i] = {{1e9, -1}, {1e9, -1}};
		shortestVis[i] = 0;
	}
	priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
	for (int root : exits) {
		dist[root] = {{0, pathInd}, {0, pathInd}};
		nodes.push({root, 0, pathInd++});
		shortestVis[root] = 2;
	}
	while (!nodes.empty()) {
		int node = nodes.top()[0];
		int minDist = nodes.top()[1];
		int pathInd = nodes.top()[2];
		nodes.pop();
		if (!shortestVis[node]) {
			shortestVis[node] = 1;
			if (pathInd != dist[node].pA.pB) {
				dist[node].pA = {minDist, pathInd};
			}
			continue;
		} else if (minDist > dist[node].pB.pA) {
			continue;
		} else if (shortestVis[node] == 1) {
			shortestVis[node]++;
		}
		for (pii i : adj[node]) {
			int neighbor = i.pA;
			int length = i.pB;
			if (minDist + length < dist[neighbor].pA.pA) {
				dist[neighbor].pB = dist[neighbor].pA;
				dist[neighbor].pA = {minDist + length, pathInd};
				nodes.push({neighbor, dist[neighbor].pA.pA, pathInd++});
			} else if (minDist + length < dist[neighbor].pB.pA) {
				dist[neighbor].pB = {minDist + length, pathInd};
				nodes.push({neighbor, dist[neighbor].pB.pA, pathInd++});
			} 
		}
	}
}

int travel_plan(int n1, int m1, int (*r1) [2], int* L, int k1, int* P) {
	n = n1;
	m = m1;
	k = k1;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		a = r1[i][0];
		b = r1[i][1];
		c = L[i];
		adj[a].pb(pii(b, c));
		adj[b].pb(pii(a, c));
	}
	FOR(i, 0, k) { 
		exits.pb(P[i]);
	}
	dijkstra();
	return dist[0].pB.pA;
}
// int main() {
// 	ios_base::sync_with_stdio(0);
// 	cin.tie(0);
// 	cin >> n >> m >> k;
// 	for (int i = 0; i < m; i++) {
// 		int a, b, c;
// 		cin >> a >> b >> c;
// 		adj[a].pb(pii(b, c));
// 		adj[b].pb(pii(a, c));
// 	}
// 	FOR(i, 0, k) {
// 		int num;
// 		cin >> num;
// 		exits.pb(num);
// 	}
// 	dijkstra();
// 	cout << dist[0].pB.pA << nl;
// }

// 5 7 2
// 0 2 4
// 0 3 3
// 3 2 2
// 2 1 10
// 0 1 100
// 0 4 7
// 3 4 9
// 1 3

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 0 / 11