Submission #515998

#	Time	Username	Problem	Language	Result	Execution time	Memory
515998		600Mihnea	Dreaming (IOI13_dreaming)	C++17	100 / 100	91 ms	24824 KiB

dreaming

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

using namespace std;


int travelTime(int n, int m, int l, int edge_a[], int edge_b[], int edge_c[]) {
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    g[edge_a[i]].push_back({edge_b[i], edge_c[i]});
    g[edge_b[i]].push_back({edge_a[i], edge_c[i]});
  }

  vector<int> dep(n, 0), up(n, 0);
  vector<bool> vis(n, 0);

  int cur_diam, cur_mx_dist;

  function<void(int)> dfs1 = [&] (int a) {

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

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

  vector<int> guys;

  int sol = 0;

  for (int r = 0; r < n; r++) {
    if (!vis[r]) {
      cur_diam = 0;
      cur_mx_dist = (int) 1e9 + 7;
      dfs1(r);
      dfs2(r);
      guys.push_back(cur_mx_dist);
      sol = max(sol, cur_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;
}

Compilation message (stderr)

dreaming.cpp: In lambda function:
dreaming.cpp:48:25: warning: unused variable 'c' [-Wunused-variable]
   48 |       int b = it.first, c = it.second;
      |                         ^

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