Submission #855381

#	Time	Username	Problem	Language	Result	Execution time	Memory
855381		tvladm2009	Dreaming (IOI13_dreaming)	C++17	100 / 100	66 ms	24916 KiB

dreaming

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

using namespace std;

typedef long long ll;
const int N = (int) 1e5 + 7;
const int INF = (int) 2e9;
int dep[N], up[N];
bool vis[N];
vector<pair<int, int>> g[N];
int n, m, l;

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  n = N;
  m = M;
  l = L;

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

  int diam, mx_dist;

  function<void(int)> dfs1 = [&] (int a) {
    vector<pair<int, int>> gg;
    vis[a] = 1;
    for (auto &b : g[a]) {
      if (!vis[b.first]) {
        gg.push_back(b);
        dfs1(b.first);
        diam = max(diam, dep[a] + dep[b.first] + b.second);
        dep[a] = max(dep[a], dep[b.first] + b.second);
      }
    }
    g[a] = gg;
  };

  function<void(int)> dfs2 = [&] (int a) {
    mx_dist = min(mx_dist, max(up[a], dep[a]));
    for (int it = 0; it < 2; it++) {
      int r = 0;
      for (auto &b : g[a]) {
        up[b.first] = max(up[b.first], up[a] + b.second);
        up[b.first] = max(up[b.first], r + b.second);
        r = max(r, dep[b.first] + b.second);
      }
      reverse(g[a].begin(), g[a].end());
    }
    for (auto &b : g[a]) {
      dfs2(b.first);
    }
  };

  vector<int> guys;
  int sol = 0;
  for (int r = 0; r < n; r++) {
    if (!vis[r]) {
      diam = 0;
      mx_dist = INF;
      dfs1(r);
      dfs2(r);
      guys.push_back(mx_dist);
      sol = max(sol, diam);
    }
  }
  sort(guys.rbegin(), guys.rend());
  if ((int) guys.size() >= 2) {
    sol = max(sol, guys[0] + guys[1] + l);
  }
  if ((int) guys.size() >= 3) {
    sol = max(sol, guys[1] + guys[2] + 2 * l);
  }
  return sol;
}

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