oj.uz

Submission #864465

# Submission time Handle Problem Language Result Execution time Memory
864465 2023-10-23T03:47:48 Z truongdoan2012 Putovanje (COCI20_putovanje) C++17
25 / 110
 65 ms 25352 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 10584 KB Output is correct
2 Incorrect 2 ms 10844 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 22372 KB Output is correct
2 Correct 52 ms 23788 KB Output is correct
3 Correct 61 ms 25352 KB Output is correct
4 Correct 65 ms 24480 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 53 ms 22096 KB Output is correct
7 Correct 32 ms 19280 KB Output is correct
8 Correct 62 ms 22100 KB Output is correct
9 Correct 45 ms 22328 KB Output is correct
10 Correct 45 ms 21584 KB Output is correct
11 Correct 47 ms 22612 KB Output is correct
12 Correct 48 ms 22612 KB Output is correct

Subtask #3
0 / 65.0

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