oj.uz

Submission #511730

# Submission time Handle Problem Language Result Execution time Memory
511730 2022-01-16T04:09:11 Z Tizariox Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 966 ms 51572 KB 
#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) { 
		return a[1] > b[1]; 
	}
};

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

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;
}
// 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;
// }

Compilation message

crocodile.cpp: In function 'void dijkstra()':
crocodile.cpp:51:7: warning: unused variable 'pathInd' [-Wunused-variable]
   51 |   int pathInd = nodes.top()[2];
      |       ^~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 5 ms 3020 KB Output is correct
13 Correct 5 ms 3020 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 5 ms 3020 KB Output is correct
13 Correct 5 ms 3020 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 632 ms 47524 KB Output is correct
17 Correct 90 ms 10808 KB Output is correct
18 Correct 158 ms 12200 KB Output is correct
19 Correct 966 ms 51572 KB Output is correct
20 Correct 250 ms 36676 KB Output is correct
21 Correct 57 ms 6276 KB Output is correct
22 Correct 363 ms 32116 KB Output is correct