oj.uz

Submission #891721

# Submission time Handle Problem Language Result Execution time Memory
891721 2023-12-23T19:07:46 Z AkibAzmain Dreaming (IOI13_dreaming) C++17
0 / 100
 33 ms 13652 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 < 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 + 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 33 ms 13652 KB Output is correct
2 Correct 32 ms 13360 KB Output is correct
3 Correct 22 ms 10320 KB Output is correct
4 Correct 5 ms 2396 KB Output is correct
5 Correct 4 ms 1884 KB Output is correct
6 Correct 8 ms 3420 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 1 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 33 ms 13652 KB Output is correct
2 Correct 32 ms 13360 KB Output is correct
3 Correct 22 ms 10320 KB Output is correct
4 Correct 5 ms 2396 KB Output is correct
5 Correct 4 ms 1884 KB Output is correct
6 Correct 8 ms 3420 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 19 ms 8636 KB Output is correct
2 Correct 20 ms 8636 KB Output is correct
3 Correct 19 ms 8668 KB Output is correct
4 Correct 21 ms 8668 KB Output is correct
5 Correct 19 ms 8668 KB Output is correct
6 Correct 20 ms 10200 KB Output is correct
7 Correct 22 ms 8924 KB Output is correct
8 Correct 19 ms 8412 KB Output is correct
9 Correct 18 ms 8564 KB Output is correct
10 Correct 20 ms 8916 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 10 ms 7220 KB Output is correct
13 Correct 10 ms 7376 KB Output is correct
14 Correct 10 ms 7120 KB Output is correct
15 Correct 9 ms 7376 KB Output is correct
16 Correct 10 ms 7120 KB Output is correct
17 Correct 9 ms 7120 KB Output is correct
18 Correct 9 ms 7376 KB Output is correct
19 Correct 10 ms 7120 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Incorrect 0 ms 440 KB Output isn't correct
22 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 1 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 33 ms 13652 KB Output is correct
2 Correct 32 ms 13360 KB Output is correct
3 Correct 22 ms 10320 KB Output is correct
4 Correct 5 ms 2396 KB Output is correct
5 Correct 4 ms 1884 KB Output is correct
6 Correct 8 ms 3420 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -