Submission #749929

#	Time	Username	Problem	Language	Result	Execution time	Memory
749929		Trunkty	Putovanje (COCI20_putovanje)	C++14	110 / 110	222 ms	49708 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,ans;
vector<vector<int>> roads[200005];
int jump[200005][21],dep[200005],one[200005],mul[200005];
int cnt[200005];

void dfs(int x, int p){
    for(vector<int> i:roads[x]){
        if(i[0]!=p){
            jump[i[0]][0] = x;
            dep[i[0]] = dep[x]+1;
            one[i[0]] = i[1];
            mul[i[0]] = i[2];
            dfs(i[0],x);
        }
    }
}

int lca(int a, int b){
    if(dep[a]>dep[b]){
        swap(a,b);
    }
    for(int j=20;j>=0;j--){
        if(dep[b]-(1<<j)>=dep[a]){
            b = jump[b][j];
        }
    }
    if(a==b){
        return a;
    }
    for(int j=20;j>=0;j--){
        if(jump[a][j]!=jump[b][j]){
            a = jump[a][j];
            b = jump[b][j];
        }
    }
    return jump[a][0];
}

void dfs2(int x, int p){
    for(vector<int> i:roads[x]){
        if(i[0]!=p){
            dfs2(i[0],x);
            cnt[x] += cnt[i[0]];
        }
    }
    ans += min(one[x]*cnt[x],mul[x]);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=1;i<=n-1;i++){
        int a,b,c1,c2;
        cin >> a >> b >> c1 >> c2;
        roads[a].push_back({b,c1,c2});
        roads[b].push_back({a,c1,c2});
    }
    dep[1] = 1;
    dfs(1,-1);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    }
    for(int i=1;i<=n-1;i++){
        int x = lca(i,i+1);
        cnt[i]++;
        cnt[i+1]++;
        cnt[x] -= 2;
    }
    dfs2(1,-1);
    cout << ans << "\n";
    return 0;
}

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