Submission #1176332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176332		_wesstiov_	Putovanje (COCI20_putovanje)	C++20	110 / 110	148 ms	64760 KiB

putovanje

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

#define pb push_back
#define fi first
#define sc second
#define fast cin.tie(0)->ios_base::sync_with_stdio(0)
#define ll long long
#define ii pair<ll,ll>
//#define int long long
const ll INF = (int)1e15;
const int max_n = (int)2e5;
const int MOD = (int)1e9 + 7;
const int LG = 17;

struct datas{
    int pos ;
    ll sum;
    int cost , cnt;
} par[max_n + 5][LG + 5];
int n;
int hig[max_n + 5];
struct node{
    int v , cost1 , cost2;
};
vector<node> adj[max_n + 5];

void dfs(int u,int p){
    for (auto v : adj[u]){
        if (v.v == p) continue;
        par[v.v][0] = {u , v.cost1 , v.cost2 , 0};
        hig[v.v] = hig[u] + 1;
        dfs(v.v , u);
    }
}

void build(){
    for (int i = 1; i <= LG ; i++){
        for (int j = 1; j <= n ; j++){
            par[j][i].pos = par[par[j][i - 1].pos][i - 1].pos;
            par[j][i].sum = par[j][i - 1].sum  + par[par[j][i - 1].pos][i - 1].sum;
        }
    }
}

ll lca(int u,int v){
    ll cost = 0;

    if (hig[u] < hig[v]) swap(u , v);

    for (int i = LG; i >= 0 ; i--){
        if (hig[v] <= hig[par[u][i].pos]) {
            cost += par[u][i].sum;
            par[u][i].cnt++;
            u = par[u][i].pos;
        }
    }

    if (u == v) return cost;

    for (int i = LG ; i >= 0 ; i--){
        if (par[u][i].pos != par[v][i].pos){
            cost += par[u][i].sum + par[v][i].sum;
            par[u][i].cnt++; par[v][i].cnt++;
            u = par[u][i].pos; v = par[v][i].pos;
        }
    }

    par[u][0].cnt++; par[v][0].cnt++;

    return cost + par[u][0].sum + par[v][0].sum;
}

signed main(){
    fast;
    //freopen("TEST.INP","r",stdin);
    //freopen("TEST.OUT","w",stdout);

    cin >> n;
    for (int i = 1; i < n ; i++){
        int u , v , cost1 , cost2; cin >> u >> v >> cost1 >> cost2 ;
        adj[u].pb({v , cost1 , cost2});
        adj[v].pb({u , cost1 , cost2});
    }

    hig[0] = -1;
    dfs(1 , 0);
    build();
    ll ans = 0;
    for (int u = 1; u < n ; u++){
        //ll a = lca(u , u + 1);
        ans +=  lca(u , u + 1);
        //cout << ans <<' ' << a <<' ' <<u <<' ' << u + 1 <<'\n';
    }

    //ll mincost = INF;

    for (int i = LG; i >= 1; i--){
        for (int j = 1; j <= n ; j++){
            par[j][i - 1].cnt += par[j][i].cnt;
            par[par[j][i - 1].pos][i - 1].cnt += par[j][i].cnt;
        }
    }

    for (int j = 2; j <= n ; j++){
        if (par[j][0].cost < par[j][0].cnt * par[j][0].sum){
            ans += par[j][0].cost - 1LL * (par[j][0].cnt * par[j][0].sum);
        }
        //cout << j <<' ' << par[j][0].pos <<' '<< par[j][0].cost <<' ' << par[j][0].cnt <<' '<<par[j][0].sum <<' ' << mincost <<'\n';
    }

    cout << ans <<'\n';
    return 0;
}

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