Submission #877967

#	Time	Username	Problem	Language	Result	Execution time	Memory
877967		LePhiPhat	Putovanje (COCI20_putovanje)	C++17	0 / 110	381 ms	63532 KiB

putovanje

#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]);
    }
    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 (stderr)

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:66:9: note: in expansion of macro 'debug'
   66 |         debug(v, dp[v]);
      |         ^~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 65