Submission #366075

#	Time	Username	Problem	Language	Result	Execution time	Memory
366075		KoD	Dreaming (IOI13_dreaming)	C++17	0 / 100	39 ms	11372 KiB

dreaming

#ifndef __APPLE__
#include "dreaming.h"
#endif
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  Vec<Vec<std::pair<int, int>>> graph(N);
  for (int i = 0; i < M; ++i) {
    A[i] -= 1;
    B[i] -= 1;
    graph[A[i]].emplace_back(B[i], T[i]);
    graph[B[i]].emplace_back(A[i], T[i]);
  }
  Vec<bool> done(N);
  Vec<Vec<int>> max(N);
  for (int i = 0; i < N; ++i) {
    max[i].resize(graph[i].size());
  }
  auto dfs = [&](auto dfs, const int u) -> int {
    done[u] = true;
    int ret = 0;
    for (int i = 0; i < (int) graph[u].size(); ++i) {
      const auto [v, c] = graph[u][i];
      if (!done[v]) {
        max[u][i] = dfs(dfs, v) + c;
        ret = std::max(ret, max[u][i]);
      }
    }
    return ret;
  };
  int ans = 0;
  auto apply = [&](auto apply, const int u, const int p, const int up) -> int {
    for (int i = 0; i < (int) graph[u].size(); ++i) {
      const auto [v, c] = graph[u][i];
      if (v == p) {
        max[u][i] = up + c;
      }
    }
    Vec<int> pref(max[u].size() + 1);
    Vec<int> suff(max[u].size() + 1);
    for (int i = 0; i < (int) max[u].size(); ++i) {
      pref[i + 1] = std::max(pref[i], max[u][i]);
      suff[i + 1] = std::max(suff[i], max[u][max[u].size() - i - 1]);
    }
    int ret = pref[max[u].size()];
    ans = std::max(ans, ret);
    for (int i = 0; i < (int) graph[u].size(); ++i) {
      ans = std::max(ans, pref[i] + suff[max[u].size() - i]);
      const auto [v, c] = graph[u][i];
      if (v != p) {
        ret = std::min(ret, apply(apply, v, u, std::max(pref[i], suff[max[u].size() - i - 1])));
      }
    }
    return ret;
  };
  Vec<int> roots;
  for (int i = 0; i < N; ++i) {
    if (!done[i]) {
      dfs(dfs, i);
      roots.push_back(apply(apply, i, i, 0));
    }
  }
  std::sort(roots.begin(), roots.end());
  const auto center = roots.back();
  roots.pop_back();
  if (roots.empty()) {
    return center;
  }
  ans = std::max(ans, center + L + roots.back());
  Vec<int> pref(roots.size() + 1);
  Vec<int> suff(roots.size() + 1);
  for (int i = 0; i < (int) roots.size(); ++i) {
    pref[i + 1] = std::max(pref[i], roots[i]);
    suff[i + 1] = std::max(suff[i], roots[roots.size() - i - 1]);
  }
  for (int i = 0; i <= (int) roots.size(); ++i) {
    ans = std::max(ans, pref[i] + suff[roots.size() - i] + 2 * L);
  }
  return ans;
}

#ifdef __APPLE__ 
int main() {
  return 0;
}
#endif

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23