oj.uz

Submission #891723

# Submission time Handle Problem Language Result Execution time Memory
891723 2023-12-23T19:10:49 Z AkibAzmain Dreaming (IOI13_dreaming) C++17
0 / 100
 31 ms 12888 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 + (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.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12888 KB Output is correct
2 Correct 31 ms 12604 KB Output is correct
3 Correct 22 ms 9564 KB Output is correct
4 Correct 5 ms 2140 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 8 ms 3164 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 1 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 31 ms 12888 KB Output is correct
2 Correct 31 ms 12604 KB Output is correct
3 Correct 22 ms 9564 KB Output is correct
4 Correct 5 ms 2140 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 8 ms 3164 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 8156 KB Output is correct
2 Correct 18 ms 8268 KB Output is correct
3 Correct 19 ms 8156 KB Output is correct
4 Correct 19 ms 8152 KB Output is correct
5 Correct 19 ms 8152 KB Output is correct
6 Correct 22 ms 9684 KB Output is correct
7 Correct 20 ms 8664 KB Output is correct
8 Correct 19 ms 8156 KB Output is correct
9 Correct 19 ms 8148 KB Output is correct
10 Correct 20 ms 8404 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 9 ms 7308 KB Output is correct
13 Correct 8 ms 7376 KB Output is correct
14 Correct 10 ms 7376 KB Output is correct
15 Correct 9 ms 7372 KB Output is correct
16 Correct 9 ms 7352 KB Output is correct
17 Correct 10 ms 7120 KB Output is correct
18 Correct 8 ms 7376 KB Output is correct
19 Correct 9 ms 7120 KB Output is correct
20 Correct 0 ms 416 KB Output is correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 31 ms 12888 KB Output is correct
2 Correct 31 ms 12604 KB Output is correct
3 Correct 22 ms 9564 KB Output is correct
4 Correct 5 ms 2140 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 8 ms 3164 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -