oj.uz

Submission #426070

# Submission time Handle Problem Language Result Execution time Memory
426070 2021-06-13T13:39:17 Z Mounir Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1239 ms 74324 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pb push_back
using namespace std;

const int N_NOEUDS = 1e6, OO = 1e9;
int dMin[N_NOEUDS][2];
bool vu[N_NOEUDS];

struct Noeud {
	int noeud, dist;

	bool operator < (const Noeud &autre) const {
		if (dist != autre.dist)
			return dist > autre.dist;
		return noeud < autre.noeud;
	}
};

vector<pii> aretes[N_NOEUDS];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int iArete = 0; iArete < M; ++iArete){
		int noeud = R[iArete][0], voisin = R[iArete][1], poids = L[iArete];
		aretes[noeud].pb({voisin, poids});
		aretes[voisin].pb({noeud, poids});
	}

	for (int noeud = 0; noeud < N; ++noeud)
		dMin[noeud][0] = dMin[noeud][1] = OO;

	priority_queue<Noeud> pq;
	for (int iSource = 0; iSource < K; ++iSource){
		int source = P[iSource];
	//	cout << "source " << source << endl;
		dMin[source][0] = dMin[source][1] = 0;
		pq.push({source, 0});
	}

	while (!pq.empty()){
		int noeud = pq.top().noeud, dist = pq.top().dist;
		pq.pop();
		if (vu[noeud]) continue;
		vu[noeud] = true;

		//cout << "pq " << noeud << " " << dist << endl;
		for (pii arete : aretes[noeud]){
			int voisin = arete.first, poids = arete.second, tot = dist + poids;
			dMin[voisin][1] = min(dMin[voisin][1], tot);
			if (dMin[voisin][1] < dMin[voisin][0])
				swap(dMin[voisin][1], dMin[voisin][0]);
			pq.push({voisin, dMin[voisin][1]});
		}
	}

	return dMin[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23756 KB Output is correct
2 Correct 18 ms 23740 KB Output is correct
3 Correct 16 ms 23784 KB Output is correct
4 Correct 16 ms 23884 KB Output is correct
5 Correct 17 ms 23884 KB Output is correct
6 Correct 17 ms 23876 KB Output is correct
7 Correct 16 ms 23820 KB Output is correct
8 Correct 14 ms 23884 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23756 KB Output is correct
2 Correct 18 ms 23740 KB Output is correct
3 Correct 16 ms 23784 KB Output is correct
4 Correct 16 ms 23884 KB Output is correct
5 Correct 17 ms 23884 KB Output is correct
6 Correct 17 ms 23876 KB Output is correct
7 Correct 16 ms 23820 KB Output is correct
8 Correct 14 ms 23884 KB Output is correct
9 Correct 18 ms 24056 KB Output is correct
10 Correct 17 ms 23788 KB Output is correct
11 Correct 18 ms 23920 KB Output is correct
12 Correct 24 ms 24308 KB Output is correct
13 Correct 25 ms 24516 KB Output is correct
14 Correct 18 ms 23848 KB Output is correct
15 Correct 15 ms 23800 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23756 KB Output is correct
2 Correct 18 ms 23740 KB Output is correct
3 Correct 16 ms 23784 KB Output is correct
4 Correct 16 ms 23884 KB Output is correct
5 Correct 17 ms 23884 KB Output is correct
6 Correct 17 ms 23876 KB Output is correct
7 Correct 16 ms 23820 KB Output is correct
8 Correct 14 ms 23884 KB Output is correct
9 Correct 18 ms 24056 KB Output is correct
10 Correct 17 ms 23788 KB Output is correct
11 Correct 18 ms 23920 KB Output is correct
12 Correct 24 ms 24308 KB Output is correct
13 Correct 25 ms 24516 KB Output is correct
14 Correct 18 ms 23848 KB Output is correct
15 Correct 15 ms 23800 KB Output is correct
16 Correct 922 ms 71612 KB Output is correct
17 Correct 148 ms 34928 KB Output is correct
18 Correct 173 ms 36240 KB Output is correct
19 Correct 1239 ms 74324 KB Output is correct
20 Correct 703 ms 64224 KB Output is correct
21 Correct 73 ms 29148 KB Output is correct
22 Correct 642 ms 55796 KB Output is correct