Submission #646150

#	Time	Username	Problem	Language	Result	Execution time	Memory
646150		Hacv16	Putovanje (COCI20_putovanje)	C++17	110 / 110	161 ms	55968 KiB

putovanje

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define sc second
#define fr first
#define all(x) x.begin(), x.end()
#define sz(x) (ll) x.size()
#define dbg(x) cerr << #x << ": [ " << x << " ]\n"

typedef long long ll;
typedef pair<int, int> pii;

const int LOG = 22;
const int MAX = 2e5 + 15;
const int INF = 0x3f3f3f3f;

struct Edge{
    ll v, c1, c2;

    Edge(ll a = 0, ll b = 0, ll c = 0){
        v = a, c1 = b, c2 = c;
    }
};

ll n, dp[MAX][LOG], dp2[MAX], d[MAX], t[MAX], w1[MAX], w2[MAX], ans;
vector<Edge> adj[MAX];

void dfs(ll u, ll p){
    dp[u][0] = p;

    for(Edge e : adj[u]){
        ll v = e.v, wc = e.c1, wt = e.c2;
        if(p == v) continue;

        d[v] = d[u] + 1;
        w1[v] = wc;
        w2[v] = wt;

        dfs(v, u);
    }
}

ll lca(ll u, ll v){
    if(d[v] > d[u]) swap(u, v);

    for(int j = LOG - 1; j >= 0; j--)
        if(d[u] - (1 << j) >= d[v]) u = dp[u][j];

    if(u == v) return v;

    for(int j = LOG - 1; j >= 0; j--){
        if(dp[u][j] != -1 && dp[u][j] != dp[v][j])
            u = dp[u][j], v = dp[v][j];
    }

    return dp[u][0];
}

void calcDp(ll u, ll p){
    for(Edge e : adj[u]){
        ll v = e.v, w1 = e.c1, w2 = e.c2;
        if(p == v) continue;

        calcDp(v, u);

        dp2[u] += dp2[v];
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    for(int i = 1; i < n; i++){
        ll u, v, wc, wt; cin >> u >> v >> wc >> wt;
        adj[u].pb(Edge(v, wc, wt));
        adj[v].pb(Edge(u, wc, wt));
    }

    memset(dp, -1, sizeof(dp));

    dfs(1, -1);

    for(int j = 1; j < LOG; j++){
        for(int i = 1; i <= n; i++){
            if(dp[i][j - 1] == -1) continue;
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }

    for(int i = 1; i < n; i++){
        ll l = lca(i, i + 1);
        dp2[i]++; dp2[i + 1]++, dp2[l] -= 2;
    }

    calcDp(1, -1);

    for(int i = 2; i <= n; i++)
        ans += min(w2[i], w1[i] * dp2[i]);

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'void calcDp(ll, ll)':
putovanje.cpp:62:21: warning: unused variable 'w1' [-Wunused-variable]
   62 |         ll v = e.v, w1 = e.c1, w2 = e.c2;
      |                     ^~
putovanje.cpp:62:32: warning: unused variable 'w2' [-Wunused-variable]
   62 |         ll v = e.v, w1 = e.c1, w2 = e.c2;
      |                                ^~

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