Submission #229235

#	Time	Username	Problem	Language	Result	Execution time	Memory
229235		VEGAnn	Putovanje (COCI20_putovanje)	C++14	110 / 110	145 ms	27384 KiB

putovanje

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
const int N = 200100;
const int PW = 20;
vector<int> vc, g[N];
int U[N], V[N], C1[N], C2[N], kol[N], n, pr[N][PW], V1[N], V2[N];
int tin[N], tout[N], tt = 0, ad[N];
ll ans = 0, sm[N];

void dfs(int v, int p){
    tin[v] = tt++;
    pr[v][0] = p;

    for (int po = 1; po < PW; po++)
        pr[v][po] = pr[pr[v][po - 1]][po - 1];

    for (int nm : g[v]){
        int u = (U[nm] == v ? V[nm] : U[nm]);

        if (u == p) continue;

        V1[u] = C1[nm];
        V2[u] = C2[nm];

        dfs(u, v);
    }

    tout[v] = tt++;
}

bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a, int b){
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;

    for (int po = PW - 1; po >= 0; po--)
        if (!upper(pr[a][po], b))
            a = pr[a][po];

    return pr[a][0];
}

void DFS(int v){
    sm[v] = 0;

    for (int nm : g[v]){
        int u = (U[nm] == v ? V[nm] : U[nm]);

        if (u == pr[v][0]) continue;

        DFS(u);
        sm[v] += sm[u];
    }

    sm[v] += ad[v];

    ans += min(ll(V1[v]) * ll(sm[v]), ll(V2[v]));
}

int main(){

    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n;

    for (int i = 1; i < n; i++){
        cin >> U[i] >> V[i] >> C1[i] >> C2[i];
        U[i]--; V[i]--;

        g[U[i]].PB(i);
        g[V[i]].PB(i);
    }

    dfs(0, 0);

    for (int i = 1; i < n; i++){
        int lc = lca(i, i - 1);

        ad[i]++;
        ad[i - 1]++;
        ad[lc] -= 2;
    }

    DFS(0);

    cout << ans;

    return 0;
}

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