Submission #891724

#	Time	Username	Problem	Language	Result	Execution time	Memory
891724		AkibAzmain	Dreaming (IOI13_dreaming)	C++17	0 / 100	36 ms	12884 KiB

dreaming

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

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
  vector < vector < pair < int, ll > > > adj (n);
  for (int i = 0; i < m; ++i)
    {
      adj[a[i]].push_back ({ b[i], (ll) t[i] });
      adj[b[i]].push_back ({ a[i], (ll) t[i] });
    }
  vector < bool > vi (n);
  vector < tuple < ll, ll, ll > > dd (n);
  auto dfs1 = [&] (auto self, int v, int p) -> ll
  {
    vi[v] = true;
    auto &[x, m, y] = dd[v];
    m = -1;
    for (auto &c : adj[v])
      if (c.first != p)
        {
          ll z = self (self, c.first, v) + c.second;
          if (z > x) y = x, x = z, m = c.first;
          else if (z > y) y = z;
        }
    return x;
  };
  auto dfs2 = [&] (auto self, int v, int p, ll z) -> pair < ll, ll >
    {
      auto &[x, m, y] = dd[v];
      if (z > x) y = x, x = z, m = p;
      else if (z > y) y = z;
      pair < ll, ll > ans = { x, v };
      for (auto &c : adj[v])
        if (c.first != p)
          ans = min (ans, self (self, c.first, v, (c.first == m ? y : x) + c.second));
      return ans;
    };
  vector < pair < ll, int > > v;
  for (int i = 0; i < n; ++i)
    if (!vi[i])
      dfs1 (dfs1, i, -1), v.push_back ({ 0, dfs2 (dfs2, i, -1, 0).second });
  for (auto &k : v) k.first = get < 0 > (dd[k.second]);
  sort (v.rbegin (), v.rend ());
  ll ii = 0;
  auto &[ix, im, iy] = dd[v[0].second];
  for (auto &[_k, k] : v)
    {
      if (!ii++) continue;
      auto &[x, m, y] = dd[k];
      auto jx = x, jy = y;

      if (ix + (ll) l > jx) jy = jx, jx = ix + (ll) l;
      else if (ix + (ll) l > jy) jy = ix + (ll) l;
      if (iy + (ll) l > jy) jy = iy + (ll) l;

      if (x + (ll) l > ix) iy = ix, ix = x + (ll) l;
      else if (x + (ll) l > iy) iy = x + (ll) l;
      if (y + (ll) l > iy) iy = y + (ll) l;

      if (jx < ix) ix = jx, iy = jy;
    }
  return ix + iy;
}

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