Submission #238255

#	Time	Username	Problem	Language	Result	Execution time	Memory
238255		Haunted_Cpp	Putovanje (COCI20_putovanje)	C++17	110 / 110	270 ms	44024 KiB

putovanje

#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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65