Submission #228379

#	Time	Username	Problem	Language	Result	Execution time	Memory
228379		tushar_2658	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	720 ms	93412 KiB

crocodile

#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std;

const int maxn = 100005;
using ll = long long;

vector<pair<int, ll>> edges[maxn];
ll dis[maxn][2];
bool vis[maxn];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{	
  for(int i = 0; i < M; ++i){
  	edges[R[i][0]].push_back(make_pair(R[i][1], L[i]));
  	edges[R[i][1]].push_back(make_pair(R[i][0], L[i]));
  }
  using pii = pair<ll, int>;
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  memset(dis, 63, sizeof dis);
  for(int i = 0; i < K; ++i){
  	pq.push(make_pair(0, P[i]));
  	dis[P[i]][0] = dis[P[i]][1] = 0;
  }
  while(!pq.empty()){
  	pii s = pq.top();
  	pq.pop();
  	if(vis[s.second])continue;
  	vis[s.second] = 1;
  	for(auto i : edges[s.second]){
  		ll cost = dis[s.second][1] + i.second;
  		if(dis[i.first][0] >= cost){
  			dis[i.first][1] = dis[i.first][0];
  			dis[i.first][0] = cost;
  			pq.push(make_pair(dis[i.first][1], i.first));
  		}else if(dis[i.first][1] > cost){
  			dis[i.first][1] = cost;
  			pq.push(make_pair(dis[i.first][1], i.first));
  		}
  	}
  }
  return dis[0][1];
}

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