Submission #1260175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260175		kawhiet	Crocodile's Underground City (IOI11_crocodile)	C++20	46 / 100	1 ms	580 KiB

crocodile

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

vector<int64_t> dp;
vector<bool> vis;
vector<vector<pair<int, int>>> g;

void dfs_set(int u, int64_t d) {
  vis[u] = 1;
  if (g[u].size() == 1) {
    dp[u] = d;
  }
  for (auto [v, w] : g[u]) {
    if (vis[v]) continue;
    dfs_set(v, d + w);
  }
}

void dfs(int u) {
  int64_t mn = 1e18, res = 1e18;
  vis[u] = 1;
  for (auto [v, w] : g[u]) {
    if (vis[v]) continue;
    dfs(v);
    if (dp[v] < mn) {
      res = mn;
      mn = dp[v];
    }
    else {
      res = min(res, dp[v]);
    }
  }
  if (g[u].size() > 1) {
    dp[u] = res;
  }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  g.resize(N);
  dp.resize(N);
  vis.resize(N);
  for (int i = 0; i < M; i++) {
    int u = R[i][0], v = R[i][1], w = L[i];
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  dfs_set(0, 0);
  fill(vis.begin(), vis.end(), 0);
  dfs(0);
  return dp[0];
}

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