oj.uz

Submission #896530

# Submission time Handle Problem Language Result Execution time Memory
896530 2024-01-01T15:45:37 Z LCJLY Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 360 ms 49608 KB 
#include "crocodile.h"
//
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
//#define int long long
vector<pii>adj[100005];

int travel_plan(int n, int m, int r[][2], int w[], int k, int p[]){
	for(int x=0;x<m;x++){
		adj[r[x][0]].push_back({r[x][1],w[x]});
		adj[r[x][1]].push_back({r[x][0],w[x]});
	}
	
	pii dist[n+5];
	//memset(dist,-1,sizeof(dist));
	for(int x=0;x<n;x++){
		dist[x]={INT_MAX,INT_MAX};
	}
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int x=0;x<k;x++){
		dist[p[x]]={0,0};
		pq.push({0,p[x]});
	}
	
	bool visited[n+5];
	memset(visited,0,sizeof(visited));
	while(!pq.empty()){
		pii cur=pq.top();
		pq.pop();
		int x=cur.second;
		int d=cur.first;
		if(dist[x].second!=d||visited[x]) continue;
		visited[x]=true;
		
		for(auto it:adj[x]){
			int nx=it.first;
			int nd=d+it.second;
			if(nd<=dist[nx].first){
				dist[nx].second=dist[nx].first;
				dist[nx].first=nd;
				pq.push({nd,nx});
			}
			else if(nd<dist[nx].second){
				dist[nx].second=nd;
				pq.push({nd,nx});
			}
		}
	}
	
	if(dist[0].second!=-1){
		return dist[0].second;
	}
	else return -1;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6580 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 1 ms 6744 KB Output is correct
11 Correct 2 ms 6744 KB Output is correct
12 Correct 3 ms 7004 KB Output is correct
13 Correct 4 ms 7004 KB Output is correct
14 Correct 1 ms 6764 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6580 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 1 ms 6744 KB Output is correct
11 Correct 2 ms 6744 KB Output is correct
12 Correct 3 ms 7004 KB Output is correct
13 Correct 4 ms 7004 KB Output is correct
14 Correct 1 ms 6764 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 298 ms 47076 KB Output is correct
17 Correct 62 ms 12228 KB Output is correct
18 Correct 68 ms 15580 KB Output is correct
19 Correct 360 ms 49608 KB Output is correct
20 Correct 219 ms 41300 KB Output is correct
21 Correct 28 ms 9296 KB Output is correct
22 Correct 228 ms 33380 KB Output is correct