oj.uz

Submission #235993

# Submission time Handle Problem Language Result Execution time Memory
235993 2020-05-30T15:48:46 Z cfalas Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 695 ms 113084 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(r[i][1],l[i]));
		adj[r[i][1]].push_back(ii(r[i][0],l[i]));
	}
	priority_queue<ii> q;
	for(int i=0;i<k;i++){
		q.push(ii(0, p[i]));
		q.push(ii(0, p[i]));
	}
	int cnt[n+1] = {};
	int ans=0;
	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;break;}
		for(auto x : adj[t.S]){
			q.push(ii(-x.S+t.F, x.F));
		}
	}
	return ans;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47352 KB Output is correct
2 Correct 30 ms 47352 KB Output is correct
3 Correct 34 ms 47360 KB Output is correct
4 Correct 31 ms 47224 KB Output is correct
5 Correct 31 ms 47488 KB Output is correct
6 Correct 31 ms 47352 KB Output is correct
7 Correct 31 ms 47480 KB Output is correct
8 Correct 30 ms 47420 KB Output is correct

Subtask #2
43.0 / 43.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47352 KB Output is correct
2 Correct 30 ms 47352 KB Output is correct
3 Correct 34 ms 47360 KB Output is correct
4 Correct 31 ms 47224 KB Output is correct
5 Correct 31 ms 47488 KB Output is correct
6 Correct 31 ms 47352 KB Output is correct
7 Correct 31 ms 47480 KB Output is correct
8 Correct 30 ms 47420 KB Output is correct
9 Correct 34 ms 47736 KB Output is correct
10 Correct 30 ms 47360 KB Output is correct
11 Correct 32 ms 47488 KB Output is correct
12 Correct 36 ms 48128 KB Output is correct
13 Correct 34 ms 48256 KB Output is correct
14 Correct 30 ms 47232 KB Output is correct
15 Correct 31 ms 47360 KB Output is correct
16 Correct 645 ms 113084 KB Output is correct
17 Correct 136 ms 60280 KB Output is correct
18 Correct 142 ms 61816 KB Output is correct
19 Correct 695 ms 108808 KB Output is correct
20 Correct 425 ms 109228 KB Output is correct
21 Correct 82 ms 52860 KB Output is correct
22 Correct 658 ms 88604 KB Output is correct