Submission #554186

#	Time	Username	Problem	Language	Result	Execution time	Memory
554186		d4xn	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	0 ms	212 KiB

crocodile

#include "crocodile.h"

#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ii pair<int, int>
#define ff first
#define ss second
#define mp make_pair
#define UB upper_bound
#define LB lower_bound
#define pb push_back
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define vii vector<ii>
#define vvii vector<vii>
#define vll vector<ll>
#define vld vector<ld>

const ll inf = 1e18;

vvii adj;
vb vis;
vll dp; // minimo tiempo para escapar des de el nodo i

int mnToExit(int u) {
  if (dp[u] != -1) return dp[u];

  vis[u] = 1;
  
  ll mn, sMn;
  mn = sMn = inf;
  for (auto &[v, w] : adj[u]) {
    if (vis[v]) continue;
    ll x = mnToExit(v) + w;
    if (x < mn) {
      sMn = mn;
      mn = x;
    }
    else if (x < sMn) {
      sMn = x;
    }
  }

  vis[u] = 0;

  return dp[u] = sMn;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  adj.resize(N);
  vis.resize(N, 0);
  dp.resize(N, -1);

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

  for (int i = 0; i < K; i++) {
    dp[P[i]] = 0;
  }

  return mnToExit(0);
}

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