oj.uz

Submission #467056

# Submission time Handle Problem Language Result Execution time Memory
467056 2021-08-21T13:38:24 Z Autron Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 643 ms 63288 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

struct elem{
	int x;
	int dist1, dist2;
	bool operator<(const elem &ot) const{
		if(dist2!=ot.dist2) return dist2>ot.dist2;
		return dist1>ot.dist1;
	}
};

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
	vector<vector<pair<int, int>>> g(n+1);
	vector<bool> used(n+1, 0);
	vector<int> dist1(n+1, 1e9), dist2(n+1, 1e9);
	priority_queue<elem> pq;
	for(int i=0;i<m;++i){
		g[r[i][0]+1].push_back({r[i][1]+1, l[i]});
		g[r[i][1]+1].push_back({r[i][0]+1, l[i]});
	}
	for(int i=0;i<k;++i){
		dist1[p[i]+1]=dist2[p[i]+1]=0;
		pq.push({p[i]+1, dist1[p[i]+1], dist2[p[i]+1]});
	}
	while(!pq.empty()){
		elem x=pq.top();
		pq.pop();
		if(used[x.x]) continue;
		used[x.x]=1;
		for(auto it:g[x.x]){
			elem nx;
			nx.x=it.first;
			nx.dist1=dist1[it.first];
			nx.dist2=dist2[it.first];
			int ndist=x.dist2+it.second;
			if(ndist<=nx.dist1){
				nx.dist2=nx.dist1;
				nx.dist1=ndist;
				pq.push(nx);
			}
			else if(ndist<nx.dist2){
				nx.dist2=ndist;
				pq.push(nx);
			}
			dist1[nx.x]=nx.dist1;
			dist2[nx.x]=nx.dist2;
		}
	}
  return dist2[1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 312 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 4 ms 844 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 4 ms 844 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 512 ms 55976 KB Output is correct
17 Correct 103 ms 15360 KB Output is correct
18 Correct 138 ms 17024 KB Output is correct
19 Correct 643 ms 63288 KB Output is correct
20 Correct 339 ms 46384 KB Output is correct
21 Correct 49 ms 6536 KB Output is correct
22 Correct 348 ms 42848 KB Output is correct