제출 #878495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878495		LePhiPhat	Putovanje (COCI20_putovanje)	C++17	110 / 110	350 ms	61376 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) {
    debug(u, k);
    for (int i = 20; i >= 0; i--) {
        if ((k & (1ll << i))) {
            u = up[u][i];
        }
    }
    debug(u);
    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 = 19; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            debug(u, v, i, 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) {
        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]++;
        debug(u, v, LCA);
        // for (int j = 1; j <= n; j++) cout << dp[j] << " \n"[j == n];
    }  
    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();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

putovanje.cpp: In function 'int jmp(int, int)':
putovanje.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42;
      |                    ^~
putovanje.cpp:35:5: note: in expansion of macro 'debug'
   35 |     debug(u, k);
      |     ^~~~~
putovanje.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42;
      |                    ^~
putovanje.cpp:41:5: note: in expansion of macro 'debug'
   41 |     debug(u);
      |     ^~~~~
putovanje.cpp: In function 'int lca(int, int)':
putovanje.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42;
      |                    ^~
putovanje.cpp:53:13: note: in expansion of macro 'debug'
   53 |             debug(u, v, i, up[u][i], up[v][i]);
      |             ^~~~~
putovanje.cpp: In function 'void solve()':
putovanje.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42;
      |                    ^~
putovanje.cpp:95:9: note: in expansion of macro 'debug'
   95 |         debug(u, v, LCA);
      |         ^~~~~

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