oj.uz

Submission #259116

# Submission time Handle Problem Language Result Execution time Memory
259116 2020-08-07T08:22:05 Z KoD Beads and wires (APIO14_beads) C++17
28 / 100
 1000 ms 1024 KB 
#line 1 "main.cpp"

/**
 * @title Template
 */

#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <tuple>
#include <cassert>
#include <random>

#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/chmin_chmax.cpp"

template <class T, class U>
constexpr bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) { 
    lhs = rhs; 
    return true; 
  }
  return false;
}

template <class T, class U>
constexpr bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) { 
    lhs = rhs; 
    return true; 
  }
  return false;
}

/**
 * @title Chmin/Chmax
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"

class range {
public:
  class iterator {
  private:
    int64_t M_position;

  public:
    constexpr iterator(int64_t position) noexcept: M_position(position) { }
    constexpr void operator ++ () noexcept { ++M_position; }
    constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
    constexpr int64_t operator * () const noexcept { return M_position; }

  };

  class reverse_iterator {
  private:
    int64_t M_position;
  
  public:
    constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }
    constexpr void operator ++ () noexcept { --M_position; }
    constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
    constexpr int64_t operator * () const noexcept { return M_position; }

  };
  
private:
  const iterator M_first, M_last;

public:
  constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
  constexpr iterator begin() const noexcept { return M_first; }
  constexpr iterator end() const noexcept { return M_last; }
  constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); } 
  constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); } 

};

/**
 * @title Range
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"

#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"

template <class T>
class rev_impl {
public:
  using iterator = typename std::decay<T>::type::reverse_iterator;

private:
  const iterator M_begin;
  const iterator M_end;

public:
  constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { }
  constexpr iterator begin() const noexcept { return M_begin; }
  constexpr iterator end() const noexcept { return M_end; }

};

template <class T>
constexpr decltype(auto) rev(T &&cont) {
  return rev_impl<T>(std::forward<T>(cont));
}

/**
 * @title Reverser
 */
#line 20 "main.cpp"

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;

constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;

struct edge_t {
  i32 to, cost;
  edge_t(i32 t, i32 c): to(t), cost(c) { }
};

i32 N;
std::vector<edge_t> graph[10000];
i32 root[10000], mid[10000];

void dfs(i32 u, i32 p) {
  root[u] = mid[u] = 0;
  i32 max_c = -inf32;
  for (auto [v, c]: graph[u]) {
    if (v == p) continue;
    dfs(v, u);
    i32 tmp = std::max(root[v], mid[v] + c);
    root[u] += tmp;
    chmax(max_c, root[v] + c - tmp);
  }
  mid[u] = root[u] + max_c;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> N;
  assert(N <= 10000);
  for (i32 i = 1; i < N; ++i) {
    i32 u, v, c;
    std::cin >> u >> v >> c;
    --u; --v;
    graph[u].emplace_back(v, c);
    graph[v].emplace_back(u, c);
  }
  i32 ans = 0;
  for (i32 src = 0; src < N; ++src) {
    dfs(src, -1);
    chmax(ans, root[src]);
  }
  std::cout << ans << '\n';
  return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 0 ms 512 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 0 ms 512 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 512 KB Output is correct
12 Correct 0 ms 512 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 0 ms 512 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 0 ms 512 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 512 KB Output is correct
12 Correct 0 ms 512 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 1 ms 640 KB Output is correct
19 Correct 1 ms 640 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 2 ms 640 KB Output is correct
22 Correct 1 ms 512 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 0 ms 512 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 0 ms 512 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 512 KB Output is correct
12 Correct 0 ms 512 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 1 ms 640 KB Output is correct
19 Correct 1 ms 640 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 2 ms 640 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 686 ms 856 KB Output is correct
24 Correct 663 ms 888 KB Output is correct
25 Correct 702 ms 888 KB Output is correct
26 Execution timed out 1090 ms 1024 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 0 ms 512 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 0 ms 512 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 512 KB Output is correct
12 Correct 0 ms 512 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 1 ms 640 KB Output is correct
19 Correct 1 ms 640 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 2 ms 640 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 686 ms 856 KB Output is correct
24 Correct 663 ms 888 KB Output is correct
25 Correct 702 ms 888 KB Output is correct
26 Execution timed out 1090 ms 1024 KB Time limit exceeded
27 Halted 0 ms 0 KB -