Submission #1179773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179773		monky-d-luffy	Putovanje (COCI20_putovanje)	C++20	110 / 110	149 ms	41076 KiB

putovanje

#include <bits/stdc++.h>
const int N = 2e5;
const int M = 2e5;
const int LOG = 20;
#define ll long long
const ll MOD = 5e6;
const ll INF = 1e9;
#define fi first
#define se second
using namespace std;

int n;
ll h[N+3], dp[N+3];
ll up[N+3][LOG+3];
vector<int> v[N+3];
ll ans = 0;

struct node{
    ll x, y, z, check;
};

vector<node> t[N+3];

void dfs(ll t){
    for(auto res : v[t]){
        if(res == up[t][0])continue;
        up[res][0] = t;
        h[res] = h[t] + 1;
        for(int i=1;i<=LOG;i++){
            up[res][i] = up[up[res][i-1]][i-1];
        }
        dfs(res);
    }
}

ll LCA(ll u, ll v){
    if(h[u] != h[v]){
        if(h[u] < h[v])swap(u, v);

        ll res = h[u] - h[v];
        for(int i=0;(1 << i) <= res;i++){
            if(res >> i & 1)u = up[u][i];
        }
    }
    if(u == v)return u;
    for(int i=__lg(h[u]);i>=0;i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i], v = up[v][i];
        }
    }
    return up[u][0];
}

void dfs2(ll t, ll p){
    for(auto res : v[t]){
        if(res == p)continue;
        dfs2(res, t);
        dp[t] += dp[res];
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("main.inp","r",stdin);
    // freopen("main.out","w",stdout);
    cin>>n;
    for(int i=1;i<n;i++){
        int x, y, a, b; cin>>x>>y>>a>>b;
        v[x].push_back(y);
        v[y].push_back(x);
        t[x].push_back({y, a, b});
    }
    dfs(1);
    for(int i=1;i<=n-1;i++){
        int lca = LCA(i, i+1);
        dp[i]++, dp[i+1]++;
        dp[lca]-=2;
    }
    dfs2(1, 0);
    for(int i=1;i<=n;i++){
        for(auto res : t[i]){
            int par;
            if(h[res.x] > h[i])par = res.x;
            else par = i;
            ll val = min(dp[par]*res.y, res.z);
            ans += val;
        }
    }
    cout<<ans<<"\n";
    return 0;
}

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