oj.uz

Submission #238255

# Submission time Handle Problem Language Result Execution time Memory
238255 2020-06-10T13:23:47 Z Haunted_Cpp Putovanje (COCI20_putovanje) C++17
110 / 110
 270 ms 44024 KB 
#include <bits/stdc++.h>
using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int MAX_N = 2e5 + 5;
const int MAX_K = 20 + 5;

vector<vector<tuple<int, int, int>>> g(MAX_N); 
vector<vector<int>> dp(MAX_N, vector<int>(MAX_K, 0));
vector<int> sum(MAX_N), depth(MAX_N);

void dfs (int node = 0, int p = -1) {
  dp[node][0] = p;
  sum[node] = 0;
  for (auto cur : g[node]) {
    int to = get<0> (cur);
    if (to != p) {
      depth[to] = depth[node] + 1;
      dfs (to, node);
    }
  }
}

int kth (int u, int d) {
  for (int i = 0; i < MAX_K; i++) {
    if ((d >> i) & 1) {
      u = dp[u][i];
    }
  }
  return u;
}

int lca (int u, int v) {
  if (depth[u] < depth[v]) swap (u, v);
  u = kth (u, depth[u] - depth[v]);
  if (u == v) return u;
  for (int i = MAX_K - 1; i >= 0; i--) {
    if (dp[u][i] != dp[v][i]) {
      u = dp[u][i];
      v = dp[v][i];
    }
  }
  return dp[u][0];
}

long long calc_sub (int node = 0, int p = -1) {
  long long res = 0;
  for (auto cur : g[node]) {
    int to = get<0> (cur);
    if (to != p) {
      res += calc_sub (to, node);
      sum[node] += sum[to];
    }
  }
  for (auto cur : g[node]) {
    int to = get<0> (cur);
    if (to == p) continue;
    int vezes = sum[to];
    long long a = 1LL * vezes * get<1> (cur);
    long long b = get<2> (cur);
    res += min (a, b);
  }
  return res;
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int st, et, one_time, mult_time;
    cin >> st >> et >> one_time >> mult_time;
    --st; --et;
    g[st].emplace_back(make_tuple(et, one_time, mult_time));
    g[et].emplace_back(make_tuple(st, one_time, mult_time));
  }
  dfs ();
  for (int j = 1; j < MAX_K; j++) {
    for (int i = 0; i < n; i++) {
      if (~dp[i][j - 1]) {
        dp[i][j] = dp[ dp[i][j - 1] ][j - 1];
      }
    }
  }
  for (int et = 1; et < n; et++) {
    int st = et - 1;
    ++sum[st];
    ++sum[et];
    sum[lca(st, et)] -= 2;
  }
  cout << calc_sub () << '\n';
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33272 KB Output is correct
2 Correct 28 ms 33280 KB Output is correct
3 Correct 30 ms 33280 KB Output is correct
4 Correct 29 ms 33280 KB Output is correct
5 Correct 30 ms 33280 KB Output is correct
6 Correct 27 ms 33280 KB Output is correct
7 Correct 27 ms 33280 KB Output is correct
8 Correct 28 ms 33280 KB Output is correct
9 Correct 29 ms 33280 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 40440 KB Output is correct
2 Correct 205 ms 41464 KB Output is correct
3 Correct 226 ms 42616 KB Output is correct
4 Correct 253 ms 44024 KB Output is correct
5 Correct 27 ms 33280 KB Output is correct
6 Correct 195 ms 41848 KB Output is correct
7 Correct 124 ms 40056 KB Output is correct
8 Correct 270 ms 42012 KB Output is correct
9 Correct 121 ms 42104 KB Output is correct
10 Correct 114 ms 41880 KB Output is correct
11 Correct 131 ms 42616 KB Output is correct
12 Correct 128 ms 42744 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33272 KB Output is correct
2 Correct 28 ms 33280 KB Output is correct
3 Correct 30 ms 33280 KB Output is correct
4 Correct 29 ms 33280 KB Output is correct
5 Correct 30 ms 33280 KB Output is correct
6 Correct 27 ms 33280 KB Output is correct
7 Correct 27 ms 33280 KB Output is correct
8 Correct 28 ms 33280 KB Output is correct
9 Correct 29 ms 33280 KB Output is correct
10 Correct 195 ms 40440 KB Output is correct
11 Correct 205 ms 41464 KB Output is correct
12 Correct 226 ms 42616 KB Output is correct
13 Correct 253 ms 44024 KB Output is correct
14 Correct 27 ms 33280 KB Output is correct
15 Correct 195 ms 41848 KB Output is correct
16 Correct 124 ms 40056 KB Output is correct
17 Correct 270 ms 42012 KB Output is correct
18 Correct 121 ms 42104 KB Output is correct
19 Correct 114 ms 41880 KB Output is correct
20 Correct 131 ms 42616 KB Output is correct
21 Correct 128 ms 42744 KB Output is correct
22 Correct 190 ms 39416 KB Output is correct
23 Correct 139 ms 38648 KB Output is correct
24 Correct 252 ms 39288 KB Output is correct
25 Correct 28 ms 33280 KB Output is correct
26 Correct 70 ms 35832 KB Output is correct
27 Correct 180 ms 38520 KB Output is correct
28 Correct 121 ms 40828 KB Output is correct
29 Correct 128 ms 42872 KB Output is correct
30 Correct 121 ms 42464 KB Output is correct
31 Correct 28 ms 33280 KB Output is correct