oj.uz

Submission #226105

# Submission time Handle Problem Language Result Execution time Memory
226105 2020-04-22T14:26:54 Z cfalas Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1090 ms 122204 KB 
#include<bits/stdc++.h>
using namespace std;
#include "crocodile.h"
#define F first
#define S second
typedef pair<int, int> ii;
typedef vector<ii> vii;

vector<vii> adj;
#define INF 1500000000
map<int, bool> child[1000000];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	adj.assign(n+1, vii());
	for(int i=0;i<m;i++){
		adj[r[i][0]].push_back(ii(l[i], r[i][1]));
		adj[r[i][1]].push_back(ii(l[i], r[i][0]));
	}
	priority_queue<ii> q;
	int cnt[n+1] = {}, ans=0;
	for(int i=0;i<k;i++){
		q.push(ii(0,p[i]));
		q.push(ii(0,p[i]));
	}
	while(!q.empty()){
		ii t = q.top();
		q.pop();
		cnt[t.S]++;
		if(cnt[t.S]!=2) continue;
		if(t.S==0) ans=-t.F;
		for(auto v : adj[t.S]){
			q.push(ii(t.F-v.F, v.S));
		}
	}
	return ans;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47352 KB Output is correct
2 Correct 29 ms 47232 KB Output is correct
3 Correct 33 ms 47480 KB Output is correct
4 Correct 31 ms 47360 KB Output is correct
5 Correct 30 ms 47360 KB Output is correct
6 Correct 30 ms 47360 KB Output is correct
7 Correct 31 ms 47352 KB Output is correct
8 Correct 30 ms 47360 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47352 KB Output is correct
2 Correct 29 ms 47232 KB Output is correct
3 Correct 33 ms 47480 KB Output is correct
4 Correct 31 ms 47360 KB Output is correct
5 Correct 30 ms 47360 KB Output is correct
6 Correct 30 ms 47360 KB Output is correct
7 Correct 31 ms 47352 KB Output is correct
8 Correct 30 ms 47360 KB Output is correct
9 Correct 32 ms 47744 KB Output is correct
10 Correct 30 ms 47480 KB Output is correct
11 Correct 31 ms 47488 KB Output is correct
12 Correct 36 ms 48128 KB Output is correct
13 Correct 35 ms 48256 KB Output is correct
14 Correct 30 ms 47336 KB Output is correct
15 Correct 30 ms 47360 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47352 KB Output is correct
2 Correct 29 ms 47232 KB Output is correct
3 Correct 33 ms 47480 KB Output is correct
4 Correct 31 ms 47360 KB Output is correct
5 Correct 30 ms 47360 KB Output is correct
6 Correct 30 ms 47360 KB Output is correct
7 Correct 31 ms 47352 KB Output is correct
8 Correct 30 ms 47360 KB Output is correct
9 Correct 32 ms 47744 KB Output is correct
10 Correct 30 ms 47480 KB Output is correct
11 Correct 31 ms 47488 KB Output is correct
12 Correct 36 ms 48128 KB Output is correct
13 Correct 35 ms 48256 KB Output is correct
14 Correct 30 ms 47336 KB Output is correct
15 Correct 30 ms 47360 KB Output is correct
16 Correct 1031 ms 117976 KB Output is correct
17 Correct 140 ms 60536 KB Output is correct
18 Correct 159 ms 61816 KB Output is correct
19 Correct 1090 ms 122204 KB Output is correct
20 Correct 742 ms 110808 KB Output is correct
21 Correct 80 ms 52984 KB Output is correct
22 Correct 658 ms 91832 KB Output is correct