oj.uz

Submission #864463

# Submission time Handle Problem Language Result Execution time Memory
864463 2023-10-23T03:42:34 Z truongdoan2012 Putovanje (COCI20_putovanje) C++17
25 / 110
 63 ms 27732 KB 
#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 = 1e5 + 10;
int up[20][N], tin[N], tout[N], t;

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

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 (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];
      v = up[i][v];
    }
  }
  return up[0][u];
}

int dp[N];
i64 ans = 0;

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

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

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB Output is correct
2 Incorrect 2 ms 11096 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 24116 KB Output is correct
2 Correct 55 ms 25428 KB Output is correct
3 Correct 60 ms 27732 KB Output is correct
4 Correct 63 ms 26708 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 58 ms 23692 KB Output is correct
7 Correct 36 ms 20564 KB Output is correct
8 Correct 57 ms 24144 KB Output is correct
9 Correct 46 ms 24144 KB Output is correct
10 Correct 46 ms 23736 KB Output is correct
11 Correct 49 ms 24876 KB Output is correct
12 Correct 51 ms 25172 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB Output is correct
2 Incorrect 2 ms 11096 KB Output isn't correct
3 Halted 0 ms 0 KB -