oj.uz

Submission #366076

# Submission time Handle Problem Language Result Execution time Memory
366076 2021-02-13T02:00:32 Z KoD Dreaming (IOI13_dreaming) C++17
0 / 100
 104 ms 22220 KB 
#ifndef __APPLE__
#include "dreaming.h"
#endif
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  Vec<Vec<std::pair<int, int>>> graph(N);
  for (int i = 0; i < M; ++i) {
    graph[A[i]].emplace_back(B[i], T[i]);
    graph[B[i]].emplace_back(A[i], T[i]);
  }
  Vec<bool> done(N);
  Vec<Vec<int>> max(N);
  for (int i = 0; i < N; ++i) {
    max[i].resize(graph[i].size());
  }
  auto dfs = [&](auto dfs, const int u) -> int {
    done[u] = true;
    int ret = 0;
    for (int i = 0; i < (int) graph[u].size(); ++i) {
      const auto [v, c] = graph[u][i];
      if (!done[v]) {
        max[u][i] = dfs(dfs, v) + c;
        ret = std::max(ret, max[u][i]);
      }
    }
    return ret;
  };
  int ans = 0;
  auto apply = [&](auto apply, const int u, const int p, const int up) -> int {
    for (int i = 0; i < (int) graph[u].size(); ++i) {
      const auto [v, c] = graph[u][i];
      if (v == p) {
        max[u][i] = up + c;
      }
    }
    Vec<int> pref(max[u].size() + 1);
    Vec<int> suff(max[u].size() + 1);
    for (int i = 0; i < (int) max[u].size(); ++i) {
      pref[i + 1] = std::max(pref[i], max[u][i]);
      suff[i + 1] = std::max(suff[i], max[u][max[u].size() - i - 1]);
    }
    int ret = pref[max[u].size()];
    ans = std::max(ans, ret);
    for (int i = 0; i < (int) graph[u].size(); ++i) {
      ans = std::max(ans, pref[i] + suff[max[u].size() - i]);
      const auto [v, c] = graph[u][i];
      if (v != p) {
        ret = std::min(ret, apply(apply, v, u, std::max(pref[i], suff[max[u].size() - i - 1])));
      }
    }
    return ret;
  };
  Vec<int> roots;
  for (int i = 0; i < N; ++i) {
    if (!done[i]) {
      dfs(dfs, i);
      roots.push_back(apply(apply, i, i, 0));
    }
  }
  std::sort(roots.begin(), roots.end());
  const auto center = roots.back();
  roots.pop_back();
  if (roots.empty()) {
    return center;
  }
  ans = std::max(ans, center + L + roots.back());
  Vec<int> pref(roots.size() + 1);
  Vec<int> suff(roots.size() + 1);
  for (int i = 0; i < (int) roots.size(); ++i) {
    pref[i + 1] = std::max(pref[i], roots[i]);
    suff[i + 1] = std::max(suff[i], roots[roots.size() - i - 1]);
  }
  for (int i = 0; i <= (int) roots.size(); ++i) {
    ans = std::max(ans, pref[i] + suff[roots.size() - i] + 2 * L);
  }
  return ans;
}

#ifdef __APPLE__ 
int A[100];
int B[100];
int T[100];
int main() {
  int N, M, L;
  std::cin >> N >> M >> L;
  for (int i = 0; i < M; ++i) {
    std::cin >> A[i] >> B[i] >> T[i];
  }
  std::cout << travelTime(N, M, L, A, B, T) << '\n';
  return 0;
}
#endif

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 21612 KB Output is correct
2 Correct 104 ms 22220 KB Output is correct
3 Correct 69 ms 19052 KB Output is correct
4 Correct 11 ms 3564 KB Output is correct
5 Correct 8 ms 2412 KB Output is correct
6 Correct 21 ms 5356 KB Output is correct
7 Incorrect 1 ms 364 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 21612 KB Output is correct
2 Correct 104 ms 22220 KB Output is correct
3 Correct 69 ms 19052 KB Output is correct
4 Correct 11 ms 3564 KB Output is correct
5 Correct 8 ms 2412 KB Output is correct
6 Correct 21 ms 5356 KB Output is correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9836 KB Output is correct
2 Correct 51 ms 10496 KB Output is correct
3 Correct 54 ms 10400 KB Output is correct
4 Correct 49 ms 10348 KB Output is correct
5 Correct 51 ms 10220 KB Output is correct
6 Correct 49 ms 10732 KB Output is correct
7 Correct 47 ms 10728 KB Output is correct
8 Correct 45 ms 10088 KB Output is correct
9 Correct 43 ms 10092 KB Output is correct
10 Correct 47 ms 10736 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 13 ms 6372 KB Output is correct
13 Correct 13 ms 6380 KB Output is correct
14 Correct 13 ms 6372 KB Output is correct
15 Correct 13 ms 6372 KB Output is correct
16 Correct 13 ms 6372 KB Output is correct
17 Correct 12 ms 6372 KB Output is correct
18 Correct 14 ms 6376 KB Output is correct
19 Correct 13 ms 6372 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Incorrect 1 ms 364 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 21612 KB Output is correct
2 Correct 104 ms 22220 KB Output is correct
3 Correct 69 ms 19052 KB Output is correct
4 Correct 11 ms 3564 KB Output is correct
5 Correct 8 ms 2412 KB Output is correct
6 Correct 21 ms 5356 KB Output is correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -