Submission #483681

#	Time	Username	Problem	Language	Result	Execution time	Memory
483681		PoPularPlusPlus	Crocodile's Underground City (IOI11_crocodile)	C++17	89 / 100	513 ms	77060 KiB

crocodile

#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] = 1e12;
	Dijkstra(p,k);
	/*for(int i = 0; i < n; i++){
		cout << dp[i] << ' ' << dp1[i] << '\n';
	}*/
	return dp1[0];
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 0 / 11