oj.uz

Submission #140372

# Submission time Handle Problem Language Result Execution time Memory
140372 2019-08-02T16:40:08 Z muradeyn Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 728 ms 61264 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxx = 100000;

int x , y;
int ext[maxx] , min1[maxx] , min2[maxx];

vector< pair<int,int> >v[maxx];

priority_queue< pair<int,int> >pq;

void dijkstra() {
	while (!pq.empty()) {
		int x = pq.top().S;
		int y = pq.top().F;
		pq.pop();
		y *= -1;
		if (!ext[x] && y > min2[x])continue;
		for (auto to : v[x]) {
			if (min1[to.F] == -1) {
				min1[to.F] = y + to.S;
				continue;
			}
			if (min2[to.F] == -1) {
				min2[to.F] = y + to.S;
				if (min2[to.F] < min1[to.F])swap(min2[to.F] , min1[to.F]);
				pq.push({-min2[to.F] , to.F});
				continue;
			}
			if (y + to.S < min1[to.F]) {
				min2[to.F] = min1[to.F];
				min1[to.F] = y + to.S;
				pq.push({-min2[to.F] , to.F});
				continue;
			}
			if (y + to.S < min2[to.F]) {
				min2[to.F] = y + to.S;
				pq.push({-min2[to.F] , to.F});
				continue;
			}
		}
	}
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	for (int i = 0;i<n;i++) min1[i] = min2[i] = -1;
	for (int i = 0;i<k;i++)ext[p[i]] = 1 , pq.push({0 , p[i]});
	for (int i = 0;i<m;i++) {
		x = r[i][0]; y = r[i][1];
		if (!ext[x])v[y].push_back({x , l[i]});
		if (!ext[y])v[x].push_back({y , l[i]});
	}
	dijkstra();
	return min2[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2728 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 2940 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 8 ms 3192 KB Output is correct
13 Correct 7 ms 3192 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2728 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 2940 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 8 ms 3192 KB Output is correct
13 Correct 7 ms 3192 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct
16 Correct 715 ms 45720 KB Output is correct
17 Correct 95 ms 13816 KB Output is correct
18 Correct 122 ms 15304 KB Output is correct
19 Correct 728 ms 61264 KB Output is correct
20 Correct 359 ms 49732 KB Output is correct
21 Correct 48 ms 7800 KB Output is correct
22 Incorrect 380 ms 46076 KB Output isn't correct