Submission #979194

#	Time	Username	Problem	Language	Result	Execution time	Memory
979194		kilkuwu	Dreaming (IOI13_dreaming)	C++17	100 / 100	58 ms	21232 KiB

dreaming

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

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

template <typename T>
inline bool ckmin(T& x, const T& y) {
  return y < x ? x = y, 1 : 0;
}

template <typename T>
inline bool ckmax(T& x, const T& y) {
  return x < y ? x = y, 1 : 0;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  dbg(N, M, L);

  auto merge = [&](int a, int b, int w) {
    int left = std::max(a, w + b);
    int right = std::max(b, w + a);
    return std::min(left, right);
  };

  std::vector<std::vector<std::pair<int, int>>> adj(N);
  for (int i = 0; i < M; i++) {
    dbg(A[i], B[i], T[i]);
    adj[A[i]].emplace_back(B[i], T[i]);
    adj[B[i]].emplace_back(A[i], T[i]);
  }


  std::priority_queue<int> pq;

  std::vector<int> vis(N), comp;
  std::vector<int> dp(N);
  std::vector<int> up(N);

  auto dfs1 = [&](auto self, int u, int p) -> void {
    comp.push_back(u);
    vis[u] = 1;
    dp[u] = 0;

    for (auto [v, w] : adj[u]) {
      if (v == p) continue;
      self(self, v, u);
      ckmax(dp[u], dp[v] + w);
    }
  };

  int max_val = 0;

  for (int i = 0; i < N; i++) {
    if (vis[i]) continue;

    auto dfs2 = [&](auto self, int u, int p) -> int {
      int lmao = std::max(up[u], dp[u]);
      ckmax(max_val, lmao);
      std::pair<int, int> good = {0, 0};

      for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        if (w + dp[v] > good.first) {
          good.second = good.first;
          good.first = w + dp[v];
        } else if (w + dp[v] > good.second) {
          good.second = w + dp[v];
        }
      }

      for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        up[v] = w + std::max(up[u], good.first == w + dp[v] ? good.second
                                                            : good.first);
        ckmin(lmao, self(self, v, u));
      }

      return lmao;
    };

    dfs1(dfs1, i, i);
    pq.push(dfs2(dfs2, i, i));
  }

  dbg(max_val);

  dbg(pq);

  dbg(pq.size());
  
  while (pq.size() > 1) {
    auto best1 = pq.top();
    pq.pop();

    auto best2 = pq.top();
    pq.pop();
    dbg(best1, best2);
    ckmax(max_val, best1 + best2 + L);

    pq.push(merge(best1, best2, L));
  }

  return max_val;
}

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