oj.uz

Submission #877973

# Submission time Handle Problem Language Result Execution time Memory
877973 2023-11-23T23:12:20 Z LePhiPhat Putovanje (COCI20_putovanje) C++17
0 / 110
 397 ms 61008 KB 
#include <bits/stdc++.h>

#ifdef LOCAL
#include "debuge.cpp"
#else
#define debug(...) 42;
#endif

using namespace std;

using ii = pair<int, int>;
using ll = long long;
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int N = 200001;
vector<int> g[N];
ll dep[N], up[N][20], dp[N];
void dfs(int u, int p) {
    up[u][0] = p;
    for (int &v: g[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
void calc(int n) {
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
}
int jmp(int u, int k) {
    for (int i = 20; i >= 0; i--) {
        if (k & (1ll << i)) {
            u = up[u][k];
        }
    }
    return u;
}
int lca(int u, int v) {
    if (dep[u] != dep[v]) {
        if (dep[u] < dep[v]) 
            swap(u, v);
        u = jmp(u, dep[u] - dep[v]);
    }
    if (u == v) return u;
    for (int i = 20; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}
void push(int u, int p) {
    for (int &v: g[u]) if (v != p) {
        push(v, u);
        dp[u] += dp[v];
    }
}
ll ans = 0;
map<pair<int, int>, ll> mp1, mp2;
void dfsAns(int u, int p) {
    for (auto &v: g[u]) if (v != p) {
        debug(v, dp[v]);
        ans += min(mp1[{u, v}] * dp[v], mp2[{u, v}]) * 1ll;
        dfsAns(v, u);
    }
}
void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        ll u, v, c1, c2;
        cin >> u >> v >> c1 >> c2;
        mp1[{u, v}] = c1;
        mp1[{v, u}] = c1;
        mp2[{u, v}] = c2;
        mp2[{v, u}] = c2;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    calc(n);
    for (int i = 1; i < n; i++) {
        int u = i, v = i + 1;
        int LCA = lca(u, v);
        dp[LCA] -= 2; 
        dp[u]++;
        dp[v]++;
    }  
    push(1, 0);   
    dfsAns(1, 0);
    cout << ans;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    #ifdef LOCAL
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
    #endif
    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
}

Compilation message

putovanje.cpp: In function 'void dfsAns(int, int)':
putovanje.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42;
      |                    ^~
putovanje.cpp:67:9: note: in expansion of macro 'debug'
   67 |         debug(v, dp[v]);
      |         ^~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 53884 KB Output is correct
2 Correct 397 ms 55940 KB Output is correct
3 Correct 309 ms 59112 KB Output is correct
4 Correct 316 ms 61008 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 315 ms 53176 KB Output is correct
7 Incorrect 166 ms 41296 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

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