Submission #1125749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125749		m_bezrutchka	Crocodile's Underground City (IOI11_crocodile)	C++20	46 / 100	5 ms	5192 KiB

crocodile

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

typedef pair<int, int> pii;
const int MAXN = 2e5 + 10;
const int INF = 1e9 + 7;
vector <pii> adj[MAXN];
bool is_exit[MAXN];
int n;
pii dp[MAXN][2];
int pai[MAXN];

void init() {
  for (int i = 1; i <= n; i++) {
    adj[i].clear();
    is_exit[i] = false;
  }
}

void dfs(int v) {
  if (is_exit[v]) {
    dp[v][0] = dp[v][1] = {0, 0};
  } else {
    dp[v][0] = dp[v][1] = {INF, -1};
  }
  for (auto [w, c]: adj[v]) {
    if (w == pai[v]) continue;
    pai[w] = v;
    // cout << "traversing edge " << v << " -> " << w << endl;
    dfs(w);
    if (dp[v][0].first > dp[w][1].first + c) {
      dp[v][1] = dp[v][0];
      dp[v][0] = {dp[w][1].first + c, w};
    } else if (dp[v][1].first > dp[w][1].first + c) {
      dp[v][1] = {dp[w][1].first + c, w};
    }
  }
  // cout << "dp[" << v << "] : (" << dp[v][0].first << " " << dp[v][0].second << ") | (" << dp[v][1].first << " " << dp[v][1].second << ")" << endl;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  n = N;
  int m = M;
  assert(m == n - 1); // subtask 1
  init();
  for (int i = 0; i < m; i++) {
    // 1-indexed
    R[i][0]++; R[i][1]++;
    adj[R[i][0]].push_back({R[i][1], L[i]});
    adj[R[i][1]].push_back({R[i][0], L[i]});
  }
  for (int i = 0; i < K; i++) {
    P[i]++;
    is_exit[P[i]] = true;
  }

  if (is_exit[1]) return 0;
  dfs(1);
  return dp[1][1].first;
}

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