oj.uz

Submission #864467

# Submission time Handle Problem Language Result Execution time Memory
864467 2023-10-23T03:51:42 Z truongdoan2012 Putovanje (COCI20_putovanje) C++17
25 / 110
 64 ms 24328 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];
}

i64 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);
    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:81:5: note: in expansion of macro 'debug'
   81 |     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 62 ms 21708 KB Output is correct
2 Correct 59 ms 23068 KB Output is correct
3 Correct 64 ms 24328 KB Output is correct
4 Correct 62 ms 23888 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 53 ms 21516 KB Output is correct
7 Correct 40 ms 18980 KB Output is correct
8 Correct 54 ms 21588 KB Output is correct
9 Correct 45 ms 21596 KB Output is correct
10 Correct 44 ms 21372 KB Output is correct
11 Correct 50 ms 22148 KB Output is correct
12 Correct 48 ms 22332 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 -