Submission #378075

#	Time	Username	Problem	Language	Result	Execution time	Memory
378075		MilosMilutinovic	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	170 ms	262148 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;

vector<vector<pair<int, int>>> g(N);
vector<bool> esc(N, false);
vector<int> dp(N, 0);

void Dfs(int u, int p) {
  if (esc[u]) {
    return;
  }
  for (auto v : g[u]) {
    if (v.first == p) {
      continue;
    }
    Dfs(v.first, u);
  }
  vector<pair<int, int>> id;
  for (auto v : g[u]) {
    if (v.first != p) {
      id.emplace_back(dp[v.first], v.second);
    }
  }
  sort(id.begin(), id.end(), [&](pair<int, int> i, pair<int, int> j) {
    return i.first + i. second < j.first + j.second;
  });
  assert((int) id.size() >= 2);
  dp[u] = id[1].first + id[1].second;
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
  for (int i = 0; i < m; i++) {
    g[r[i][0]].emplace_back(r[i][1], l[i]);
    g[r[i][1]].emplace_back(r[i][0], l[i]);
  }
  for (int i = 0; i < k; i++) {
    esc[p[i]] = true;
  }
  Dfs(0, -1);
  return dp[0];
}

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