Submission #492068

#	Time	Username	Problem	Language	Result	Execution time	Memory
492068		lorenzoferrari	Dreaming (IOI13_dreaming)	C++17	100 / 100	106 ms	18372 KiB

dreaming

#include <bits/stdc++.h>
#ifndef LORENZO
#include "dreaming.h"
#endif
using namespace std;
using ll = long long;

array<int, 2> dmax;
vector<int> id, d;
vector<vector<int>> cc;
vector<vector<pair<int, int>>> g;

void comps(int v) {
  if (id[v] != -1) return;
  id[v] = cc.size() - 1;
  cc.back().push_back(v);
  for (auto [u, w] : g[v])
    comps(u);
}

void dfs(int v, int p) {
  if (d[v] > dmax[1]) dmax = {v, d[v]};
  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    d[u] = d[v] + w;
    dfs(u, v);
  }
}

int diam(int v) {
  dmax = {v, 0}; dfs(v, -1);
  v = dmax[0]; d[v] = 0;
  dmax = {v, 0}; dfs(v, -1);
  return dmax[1];
}

bool rebuild(int v, int p, int target, vector<int>& archi) {
  if (v == target) return true;
  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    if (rebuild(u, v, target, archi)) {
      archi.push_back(w);
      return true;
    }
  }
  return false;
}

int coda(int v) {
  dmax = {v, 0}; dfs(v, -1);
  int a = dmax[0]; d[a] = 0;
  dmax = {a, 0}; dfs(a, -1);
  int b = dmax[0];

  vector<int> archi; // archi del diametro
  assert(rebuild(a, -1, b, archi));

  int sum = 0;
  for (int w : archi) sum += w;
  int ans = sum;
  for (int i = 0, p = 0; i < int(archi.size()); ++i) {
    p += archi[i];
    ans = min(ans, max(sum - p, p));
  }
  return ans;

  // modo stupido O(n^2)
  ans = 1e9;
  for (int u : cc[id[v]]) {
    fill(d.begin(), d.end(), 0);
    dfs(u, -1);
    ans = min(ans, *max_element(d.begin(), d.end()));
  }
  // cout << "coda[" << v << "] = " << ans << "\n";
  return ans;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  g.resize(N);
  d.resize(N);
  id.resize(N, -1);
  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]});
  }
  for (int i = 0; i < N; ++i) {
    if (id[i] == -1) {
      cc.push_back(vector<int>(0));
      comps(i);
    }
  }
  int ans = 0;
  for (int i = 0; i < int(cc.size()); ++i)
    ans = max(ans, diam(cc[i][0]));
  array<int, 3> o{};
  for (int i = 0; i < int(cc.size()); ++i) {
    o[2] = max(o[2], coda(cc[i][0]));
    if (o[1] < o[2]) swap(o[1], o[2]);
    if (o[0] < o[1]) swap(o[0], o[1]);
  }
  // cout << o[0] << " " << o[1] << " " << o[2] << "\n";
  if (int(cc.size()) == 1) return ans;
  ans = max(ans, o[0] + o[1] + L);
  if (int(cc.size()) == 2) return ans;
  ans = max(ans, o[1] + o[2] + 2*L);
  return ans;
}

#ifdef LORENZO
  int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n, m, l;
    cin >> n >> m >> l;
    int a[100], b[100], t[100];
    for (int i = 0; i < m; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    for (int i = 0; i < m; ++i) cin >> t[i];
    cout << travelTime(n, m, l, a, b, t) << "\n";
  }
  #endif

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