Submission #649606

#	Time	Username	Problem	Language	Result	Execution time	Memory
649606		AkiYuu	Putovanje (COCI20_putovanje)	C++17	110 / 110	112 ms	46092 KiB

putovanje

/*

Author: AkiYuu
TASK:
LANG: C++14

*/

#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb push_back
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()

using namespace std;

void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen(task".inp", "r", stdin);
//	freopen(task".out", "w", stdout);
}

const int mxn = 1e6 + 5;
typedef pair<ll, ll> ii;

vector < ii > a[mxn];
int up[20][mxn], tin[mxn], tout[mxn], timer;
ll add[mxn];
int n;
ll cost[2][mxn];
int edge[mxn];
ll ans = 0;

void dfs(int u, int p ){
    tin[u] = ++timer;
    up[0][u] = p;

    for ( ii x : a[u]){
        int v = x.first, id = x.second;
        if ( v == p ) continue;
        dfs(v,u);
        edge[v] = id;
    }

    tout[u] = timer;
}

bool ispar(int u , int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v){
    if (ispar(u,v) ) return u;
    if (ispar(v,u) )  return v;
    fbw(i,18,0) if (!ispar(up[i][u], v)) u= up[i][u];
    return up[0][u];
}

void get(int u, int p = -1){

    for ( ii x : a[u]) {
        int v = x.first, id = x.second;
        if (v == p ) continue;
        get(v,u);
        add[u] += add[v];
    }
    int Eid = edge[u];
    ans += min( cost[0][Eid] * add[u], cost[1][Eid] );
}

void solve(){

    cin >> n;

    ffw(i,1,n-1){
        int u , v;
        cin >> u >> v >> cost[0][i] >> cost[1][i];
        a[u].pb(ii(v,i));
        a[v].pb(ii(u,i));
    }

    dfs(1,1);

    ffw(i,1,18) ffw(j,1,n){
        up[i][j] = up[i-1][ up[i-1][j] ];
    }
    
    ffw(i,1,n-1){
        int u = i, v = i + 1, c = lca(u,v);
        add[u]++;
        add[v]++;
        add[c] -= 2;
    }


    get(1);
    cout << ans;
}

int main(){
	fastio();
	int t = 1;
//	cin >> t;
	while (t--)
	solve();
}

Compilation message (stderr)

putovanje.cpp: In function 'void get(int, int)':
putovanje.cpp:70:26: warning: unused variable 'id' [-Wunused-variable]
   70 |         int v = x.first, id = x.second;
      |                          ^~

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