Submission #483905

#	Time	Username	Problem	Language	Result	Execution time	Memory
483905		evenvalue	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	151 ms	262148 KiB

crocodile

#include "crocodile.h"
#include <vector>
using namespace std;

struct edge {
  int x;
  int y;
  int w;
};

class solution {
  const int kInf = 1e9 + 10;
  const int n;
  const int m;
  const vector<edge> edges;
  const int k;
  const vector<int> end;
  vector<vector<pair<int, int>>> g;
  vector<int> dp;

  int dfs(const int x, const int p) {
    if (dp[x] == 0) return 0;
    int mn = kInf, mn2 = kInf;
    for (const auto &[y, w] : g[x]) {
      if (y == p) continue;
      const int cur = dfs(y, x) + w;
      if (cur < mn) {
        mn2 = mn;
        mn = cur;
      } else {
        mn2 = min(mn2, cur);
      }
    }
    return (dp[x] = mn2);
  }

public:
  explicit solution(const int n, const vector<edge> &edges, const vector<int> &end) : n(n), m(edges.size()), edges(edges), k(end.size()), end(end), g(n), dp(n, kInf) {
    for (const auto &[x, y, w] : edges) {
      g[x].emplace_back(y, w);
      g[y].emplace_back(x, w);
    }
    for (const int x : end) dp[x] = 0;
  }

  int solve() {
    return dfs(0, -1);
  }
};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  vector<edge> edges(M);
  for (int i = 0; i < M; i++) {
    edges[i].x = R[i][0];
    edges[i].y = R[i][1];
    edges[i].w = L[i];
  }
  vector<int> end(K);
  for (int i = 0; i < K; i++) {
    end[i] = P[i];
  }
  solution s(N, edges, end);
  return s.solve();
}

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