Submission #864472

#	Time	Username	Problem	Language	Result	Execution time	Memory
864472		truongdoan2012	Putovanje (COCI20_putovanje)	C++17	110 / 110	76 ms	35412 KiB

putovanje

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

using i64 = long long;

const int N = 2e5 + 10;
int up[20][N], tin[N], tout[N], t;

struct edge {
  int to = 0;
  i64 c1 = 0, c2 = 0;
};

vector<edge> g[N];

void dfs(int u, int p) {
  up[0][u] = p;
  tin[u] = t++;
  for (int i = 1; i < 20; i++) {
    up[i][u] = up[i - 1][up[i - 1][u]];
  }
  for (const auto& v : g[u]) {
    if (v.to == p) continue;
    dfs(v.to, u);
  }
  tout[u] = t++;
}

int n;
bool line(int u, int v) {
  return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
  if (line(u, v)) return u;
  if (line(v, u)) return v;
  for (int i = 19; i >= 0; i--) {
    if (!line(up[i][u], v)) {
      u = up[i][u];
    }
  }
  return up[0][u];
}

i64 dp[N];
i64 ans = 0;

void calc(int u, int p) {
  for (const auto& v : g[u]) {
    if (v.to == p) continue;
    calc(v.to, u);
    ans += min(v.c1 * dp[v.to], v.c2);
    dp[u] += dp[v.to];
  }  
}

void solve() {
  cin >> n;  
  for (int i = 0; i < n - 1; i++) {
    int a, b, c1, c2;
    cin >> a >> b >> c1 >> c2;
    g[a].push_back({b, c1, c2});
    g[b].push_back({a, c1, c2});
  }
  dfs(1, 1);
  for (int i = 1; i < n; i++) {
    dp[i]++;
    dp[i + 1]++;
    dp[lca(i, i + 1)] -= 2;
  }
  calc(1, 1);
  for (int i = 0; i < n; i++) {
    debug(dp[i]);
  }
  cout << ans;
}

int main() {
  cin.tie(nullptr) -> sync_with_stdio(false);
  int TC = 1;
  //cin >> TC;
  while (TC--) {
    solve();
  }
}

Compilation message (stderr)

putovanje.cpp: In function 'void solve()':
putovanje.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 42
      |                    ^~
putovanje.cpp:80:5: note: in expansion of macro 'debug'
   80 |     debug(dp[i]);
      |     ^~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65