oj.uz

Submission #50991

# Submission time Handle Problem Language Result Execution time Memory
50991 2018-06-15T13:22:57 Z win11905 Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 828 ms 45112 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int MXN = 1e5+5, INF = 1e9+1;

pii d[MXN];
vector<vector<pii> > g(MXN);

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for(int i = 0, u, v, w; i < M; ++i) {
		u = R[i][0], v = R[i][1], w = L[i];
		g[u].emplace_back(v, w), g[v].emplace_back(u, w);
	}
	fill(d, d+N, pii(INF, INF));
	priority_queue<pii, vector<pii>, greater<pii> > Q;
	for(int i = 0; i < K; ++i) d[P[i]] = pii(0, 0), Q.emplace(0, P[i]);
	while(!Q.empty()) {
		pii now = Q.top(); Q.pop();
		if(d[now.y].y != now.x) continue;
		for(auto v : g[now.y]) {
			int z = now.x + v.y;
			if(d[v.x].x > z) swap(d[v.x].x, z);
			if(d[v.x].y > z) swap(d[v.x].y, z), Q.emplace(d[v.x].y, v.x);
		}
	}
	return d[0].y;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 4 ms 2788 KB Output is correct
4 Correct 4 ms 2880 KB Output is correct
5 Correct 4 ms 2880 KB Output is correct
6 Correct 4 ms 2940 KB Output is correct
7 Correct 4 ms 3016 KB Output is correct
8 Correct 5 ms 3032 KB Output is correct

Subtask #2
43.0 / 43.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 41208 KB Output is correct
2 Correct 98 ms 41208 KB Output is correct
3 Correct 131 ms 41208 KB Output is correct
4 Correct 828 ms 45112 KB Output is correct
5 Correct 427 ms 45112 KB Output is correct
6 Correct 47 ms 45112 KB Output is correct
7 Correct 382 ms 45112 KB Output is correct