Submission #1209408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209408		kunzaZa183	Dreaming (IOI13_dreaming)	C++20	100 / 100	93 ms	29256 KiB

dreaming

#include "dreaming.h"

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

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  vector<vector<pair<int, int>>> vvi(N);
  for (int i = 0; i < M; i++)
    vvi[A[i]].push_back({B[i], T[i]}), vvi[B[i]].push_back({A[i], T[i]});

  vector<int> dp(N);
  vector<bool> visi(N);

  function<int(int)> fii = [&](int cur) -> int {
    if (visi[cur]) return -1e9;
    visi[cur] = 1;

    for (auto& a : vvi[cur]) {
      dp[cur] = max(dp[cur], fii(a.first) + a.second);
    }

    return dp[cur];
  };

  for (int i = 0; i < N; i++) {
    fii(i);
  }

  vector<int> dp2(N);
  visi.assign(N, 0);
  function<void(int, int)> fii2 = [&](int cur, int up) {
    if (visi[cur]) return;
    visi[cur] = 1;
    dp2[cur] = up;

    multiset<int> si = {up};

    for (auto a : vvi[cur]) {
      if (visi[a.first] == 1) continue;
      si.insert(a.second + dp[a.first]);
    }

    for (auto a : vvi[cur]) {
      if (visi[a.first] == 1) continue;
      si.erase(si.find(a.second + dp[a.first]));

      fii2(a.first, a.second + *si.rbegin());

      si.insert(a.second + dp[a.first]);
    }
  };

  for (int i = 0; i < N; i++) {
    fii2(i, 0);
  }

  vector<int> compo(N, -1);
  function<void(int, int)> fii3 = [&](int cur, int comp) {
    if (compo[cur] != -1) return;
    compo[cur] = comp;
    for (auto a : vvi[cur]) fii3(a.first, comp);
  };
  int cur = 0;
  for (int i = 0; i < N; i++) {
    if (compo[i] == -1) fii3(i, cur++);
  }

  vector<int> all(cur, 1e9);
  for (int i = 0; i < N; i++) {
    all[compo[i]] = min(all[compo[i]], max(dp[i], dp2[i]));
  }
  sort(all.rbegin(), all.rend());

  int biggest = max(*max_element(dp.begin(), dp.end()),
                    *max_element(dp2.begin(), dp2.end()));

  if (cur == 1) {
    return max(biggest, all[0]);
  } else if (cur == 2) {
    return max(biggest, all[0] + all[1] + L);
  } else {
    return max({biggest, all[0] + all[1] + L, all[1] + all[2] + 2 * 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