Submission #978875

#	Time	Username	Problem	Language	Result	Execution time	Memory
978875		badont	Dreaming (IOI13_dreaming)	C++17	100 / 100	64 ms	16144 KiB

dreaming

#include "dreaming.h"
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  ll n = N, m = M, l = L;
  vector e(n, vector<pii>());

  vector<int> par(n, -1);
  vector<bool> v(n, false);
  vector<ll> dist(n, 0);

  for (int i = 0; i < m; i++) {
    e[A[i]].push_back({B[i], T[i]});
    e[B[i]].push_back({A[i], T[i]});
  }

  ll ans = 0;
  vector<ll> a;
  for (int c = 0; c < n; c++) {
    if (v[c])
      continue;

    vector<ll> comp;
    bool push_comp = true;
    auto dfs_1 = [&](auto &dfs, int g, int p, ll d) -> void {
      dist[g] = d;
      v[g] = true;
      par[g] = p;
      if (push_comp) {
        comp.push_back(g);
      }
      for (auto [u, xd] : e[g]) {
        if (u == p)
          continue;
        dfs(dfs, u, g, d + xd);
      }
    };
    dfs_1(dfs_1, c, -1, 0);
    ll max_dist = 0, root = c;
    for (auto u : comp) {
      if (dist[u] > max_dist) {
        max_dist = dist[u];
        root = u;
      }
    }
    push_comp = false;
    dfs_1(dfs_1, root, -1, 0);
    max_dist = 0;
    int root_2 = root;
    for (auto u : comp) {
      if (dist[u] > max_dist) {
        max_dist = dist[u];
        root_2 = u;
      }
    }

    int cur = root_2;
    ll h = max_dist;
    while (par[cur] != -1) {
      ll d1 = dist[cur], d2 = max_dist - dist[cur];
      h = min(h, max(d1, d2));
      cur = par[cur];
    }
    ans = max(ans, max_dist);
    a.push_back(h);
  }
  sort(a.begin(), a.end(), greater<ll>());
  if ((int)a.size() >= 2) {
    ans = max(ans, a[0] + a[1] + L);
  }
  if ((int)a.size() >= 3) {
    ans = max(ans, a[1] + a[2] + 2 * L);
  }
  return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:10:20: warning: unused variable 'l' [-Wunused-variable]
   10 |   ll n = N, m = M, l = L;
      |                    ^

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