Submission #1260172

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

crocodile

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

vector<int64_t> dp, c;
vector<vector<pair<int, int>>> g;

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

void dfs(int u, int p) {
  int64_t mn = 1e18, res = 1e18;
  for (auto [v, w] : g[u]) {
    if (v == p) continue;
    dfs(v, u);
    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[]) {
  c.resize(N + 1);
  g.resize(N + 1);
  dp.resize(N + 1);
  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, -1, 0);
  dfs(0, -1);
  return dp[0];
}

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