oj.uz

Submission #891718

# Submission time Handle Problem Language Result Execution time Memory
891718 2023-12-23T18:13:35 Z AkibAzmain Dreaming (IOI13_dreaming) C++17
0 / 100
 31 ms 12892 KB 
#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 < int > v;
  for (int i = 0; i < n; ++i)
    if (!vi[i])
      dfs1 (dfs1, i, -1), v.push_back (dfs2 (dfs2, i, -1, 0).second);
  ll ii = 0;
  auto &[ix, im, iy] = dd[v[0]];
  for (auto &k : v)
    {
      if (!ii++) continue;
      auto &[x, m, y] = dd[k];
      auto jx = x, jy = y;

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

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

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12892 KB Output is correct
2 Correct 31 ms 12488 KB Output is correct
3 Correct 23 ms 9412 KB Output is correct
4 Correct 5 ms 2140 KB Output is correct
5 Correct 4 ms 1568 KB Output is correct
6 Correct 8 ms 3344 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12892 KB Output is correct
2 Correct 31 ms 12488 KB Output is correct
3 Correct 23 ms 9412 KB Output is correct
4 Correct 5 ms 2140 KB Output is correct
5 Correct 4 ms 1568 KB Output is correct
6 Correct 8 ms 3344 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7512 KB Output is correct
2 Incorrect 14 ms 7516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12892 KB Output is correct
2 Correct 31 ms 12488 KB Output is correct
3 Correct 23 ms 9412 KB Output is correct
4 Correct 5 ms 2140 KB Output is correct
5 Correct 4 ms 1568 KB Output is correct
6 Correct 8 ms 3344 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -