oj.uz

Submission #483680

# Submission time Handle Problem Language Result Execution time Memory
483680 2021-10-31T17:03:44 Z PoPularPlusPlus Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 505 ms 81952 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

vector<pair<int,ll>	> adj[100002];
ll dp[100002],dp1[100002];

void Dijkstra(int p[] , int k){
	 priority_queue< pair<ll,ll>, vector <pair<ll,ll>> , greater<pair<ll,ll>> > pq; 
	 for(int e = 0; e < k; e++){
		 dp[p[e]] = dp1[p[e]] = 0;
		 pq.push({dp1[p[e]] , p[e]});
	 }
	 while(!pq.empty()){
		 ll node = pq.top().second,ww=pq.top().first;
		 pq.pop();
		 if(dp1[node] < ww)continue;
		 for(auto i : adj[node]){
			 ll w = i.second;
			 if(dp[i.first] >ww + w){
				 dp1[i.vf] = dp[i.vf];
				 dp[i.vf] = ww + w;
				 pq.push({dp1[i.first],i.first});
			 }
			 else if(dp1[i.vf] > ww + w){
				 dp1[i.vf] = ww + w;
				 pq.push({dp1[i.first],i.first});
			 }
		 }
	 }
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
	for(int i = 0; i < m; i++){
		adj[r[i][0]].pb(mp(r[i][1] , l[i]));
		adj[r[i][1]].pb(mp(r[i][0] , l[i]));
	}
	for(int i = 0; i < n; i++)dp[i] = dp1[i] = 1e18;
	Dijkstra(p,k);
	/*for(int i = 0; i < n; i++){
		cout << dp[i] << ' ' << dp1[i] << '\n';
	}*/
	return dp1[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 3020 KB Output is correct
10 Correct 1 ms 2636 KB Output is correct
11 Correct 2 ms 2832 KB Output is correct
12 Correct 5 ms 3404 KB Output is correct
13 Correct 5 ms 3404 KB Output is correct
14 Correct 2 ms 2660 KB Output is correct
15 Correct 2 ms 2796 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 3020 KB Output is correct
10 Correct 1 ms 2636 KB Output is correct
11 Correct 2 ms 2832 KB Output is correct
12 Correct 5 ms 3404 KB Output is correct
13 Correct 5 ms 3404 KB Output is correct
14 Correct 2 ms 2660 KB Output is correct
15 Correct 2 ms 2796 KB Output is correct
16 Correct 391 ms 73656 KB Output is correct
17 Correct 84 ms 19780 KB Output is correct
18 Correct 106 ms 22196 KB Output is correct
19 Correct 505 ms 81952 KB Output is correct
20 Correct 261 ms 59972 KB Output is correct
21 Correct 41 ms 10432 KB Output is correct
22 Incorrect 280 ms 55448 KB Output isn't correct