Submission #919878

#	Time	Username	Problem	Language	Result	Execution time	Memory
919878		mariaclara	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	626 ms	57636 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5+5;
#define all(x) x.begin(), x.end()
#define mk make_pair
#define pb push_back 
#define fr first 
#define sc second

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {

  int min_cost[N], cost[N];
  bool vis[N];
  vector<pii> edges[N];
  memset(vis, 0, sizeof(vis));
  fill(cost, cost+N, 1e9+7);
  fill(min_cost, min_cost+N, 1e9+7);

  for(int i = 0; i < M; i++)
    edges[R[i][0]].pb({R[i][1], L[i]}), edges[R[i][1]].pb({R[i][0], L[i]});

  priority_queue<pii, vector<pii>, greater<pii>> pq;

  for(int i = 0; i < K; i++)
    pq.push({0, P[i]}), min_cost[P[i]] = cost[P[i]] = 0;

  while(!pq.empty()) {
    auto [d, x] = pq.top();
    pq.pop();
    if(vis[x]) continue;
    vis[x] = 1; 

    for(auto [viz, peso] : edges[x]) {
      cost[viz] = min(cost[viz], max(min_cost[viz], d + peso));
      min_cost[viz] = min(min_cost[viz], d + peso);

      if(cost[viz] < 1e9+7) pq.push({cost[viz], viz});
    }
  }

  return cost[0];
}

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