oj.uz

Submission #864471

# Submission time Handle Problem Language Result Execution time Memory
864471 2023-10-23T03:53:35 Z truongdoan2012 Putovanje (COCI20_putovanje) C++17
25 / 110
 70 ms 34608 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];
      v = up[i][v];
    }
  }
  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: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 3 ms 22876 KB Output is correct
2 Incorrect 4 ms 23128 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 58 ms 32440 KB Output is correct
2 Correct 55 ms 33368 KB Output is correct
3 Correct 70 ms 34608 KB Output is correct
4 Correct 64 ms 34132 KB Output is correct
5 Correct 4 ms 22876 KB Output is correct
6 Correct 60 ms 32152 KB Output is correct
7 Correct 36 ms 29912 KB Output is correct
8 Correct 60 ms 32324 KB Output is correct
9 Correct 46 ms 32336 KB Output is correct
10 Correct 44 ms 31956 KB Output is correct
11 Correct 48 ms 32664 KB Output is correct
12 Correct 51 ms 32764 KB Output is correct

Subtask #3
0 / 65.0

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