oj.uz

Submission #864472

# Submission time Handle Problem Language Result Execution time Memory
864472 2023-10-23T03:56:24 Z truongdoan2012 Putovanje (COCI20_putovanje) C++17
110 / 110
 76 ms 35412 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 = 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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 4 ms 23132 KB Output is correct
3 Correct 4 ms 23132 KB Output is correct
4 Correct 5 ms 23132 KB Output is correct
5 Correct 4 ms 23132 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 22876 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 4 ms 23132 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 32336 KB Output is correct
2 Correct 54 ms 33360 KB Output is correct
3 Correct 60 ms 34640 KB Output is correct
4 Correct 61 ms 34128 KB Output is correct
5 Correct 3 ms 22872 KB Output is correct
6 Correct 52 ms 32160 KB Output is correct
7 Correct 36 ms 30032 KB Output is correct
8 Correct 56 ms 32084 KB Output is correct
9 Correct 46 ms 32348 KB Output is correct
10 Correct 48 ms 32336 KB Output is correct
11 Correct 47 ms 32844 KB Output is correct
12 Correct 47 ms 32852 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 4 ms 23132 KB Output is correct
3 Correct 4 ms 23132 KB Output is correct
4 Correct 5 ms 23132 KB Output is correct
5 Correct 4 ms 23132 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 22876 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 4 ms 23132 KB Output is correct
10 Correct 53 ms 32336 KB Output is correct
11 Correct 54 ms 33360 KB Output is correct
12 Correct 60 ms 34640 KB Output is correct
13 Correct 61 ms 34128 KB Output is correct
14 Correct 3 ms 22872 KB Output is correct
15 Correct 52 ms 32160 KB Output is correct
16 Correct 36 ms 30032 KB Output is correct
17 Correct 56 ms 32084 KB Output is correct
18 Correct 46 ms 32348 KB Output is correct
19 Correct 48 ms 32336 KB Output is correct
20 Correct 47 ms 32844 KB Output is correct
21 Correct 47 ms 32852 KB Output is correct
22 Correct 66 ms 31712 KB Output is correct
23 Correct 63 ms 30800 KB Output is correct
24 Correct 76 ms 31668 KB Output is correct
25 Correct 4 ms 23128 KB Output is correct
26 Correct 28 ms 26792 KB Output is correct
27 Correct 55 ms 30552 KB Output is correct
28 Correct 39 ms 32848 KB Output is correct
29 Correct 52 ms 35412 KB Output is correct
30 Correct 47 ms 34996 KB Output is correct
31 Correct 4 ms 23132 KB Output is correct