Submission #659699

#	Time	Username	Problem	Language	Result	Execution time	Memory
659699		hjcafaroUC	Putovanje (COCI20_putovanje)	C++17	110 / 110	102 ms	27380 KiB

putovanje

//
//  Created by Henry Cafaro
//  Copyright © 2020 Henry Cafaro. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}

#else
#define dbg(x)
#endif
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}


// === Debug macro ends here ===

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct FT {
	vector<ll> s;
	FT(int n) : s(n) {}
	void update(int pos, ll dif) { // a[pos] += dif
		for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
	}
	ll query(int pos) { // sum of values in [0, pos)
		ll res = 0;
		for (; pos > 0; pos &= pos - 1) res += s[pos-1];
		return res;
	}
	int lower_bound(ll sum) {// min pos st sum of [0, pos] >= sum
		// Returns n if no sum is >= sum, or -1 if empty sum is.
		if (sum <= 0) return -1;
		int pos = 0;
		for (int pw = 1 << 25; pw; pw >>= 1) {
			if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
				pos += pw, sum -= s[pos-1];
		}
		return pos;
	}
};

vector<vi> treeJump(vi& P){
	int on = 1, d = 1;
	while(on < sz(P)) on *= 2, d++;
	vector<vi> jmp(d, P);
	rep(i,1,d) rep(j,0,sz(P))
		jmp[i][j] = jmp[i-1][jmp[i-1][j]];
	return jmp;
}

int jmp(vector<vi>& tbl, int nod, int steps){
	rep(i,0,sz(tbl))
		if(steps&(1<<i)) nod = tbl[i][nod];
	return nod;
}

int lca(vector<vi>& tbl, vi& depth, int a, int b) {
	if (depth[a] < depth[b]) swap(a, b);
	a = jmp(tbl, a, depth[a] - depth[b]);
	if (a == b) return a;
	for (int i = sz(tbl); i--;) {
		int c = tbl[i][a], d = tbl[i][b];
		if (c != d) a = c, b = d;
	}
	return tbl[0][a];
}

int n;

struct edge {
    int nxt;
    ll c1;
    ll c2;
};

vector<vector<edge>> adj;
vector<int> p;
vector<int> ht;
vector<int> tin;
vector<int> tout;
vector<ll> cs1;
vector<ll> cs2;

int gt = 0;

void dfs(int x, int par, int h){
    dbg(x);
    
    ht[x] = h;
    tin[x] = gt++;

    for(auto [nxt, c1, c2] : adj[x]){
        if(nxt == par)
            continue;
        p[nxt] = x;
        cs1[nxt] = c1;
        cs2[nxt] = c2;
        dfs(nxt, x, h+1);
    }

    tout[x] = gt++;
}

void solve(){
    cin >> n;

    adj.resize(n);
    cs1.resize(n);
    cs2.resize(n);
    p.resize(n);
    ht.resize(n);
    dbg(ht);
    dbg(n);
    tin.resize(n);
    tout.resize(n);

    

    for(int i = 0; i < n-1; i++){
        int a,b;
        ll c1,c2;
        cin >> a >> b >> c1 >> c2;
        a--;b--;

        adj[a].push_back({b,c1,c2});
        adj[b].push_back({a,c1,c2});

    }



    dfs(0, -1, 0);

    dbg(ht);
    dbg(p);
    dbg(tin);
    dbg(tout);
    dbg(cs1);
    dbg(cs2);

    auto jt = treeJump(p);

    auto ft = FT(2*n+2);

    for(int i = 0; i+1 < n; i++){
        int l = lca(jt, ht, i, i+1);
        dbg(l);
        ft.update(tin[i], 1);
        ft.update(tin[i+1], 1);
        ft.update(tin[l], -2);
    }

    ll ans = 0;

    for(int i = 0; i < n; i++){
        dbg(i);
        dbg(ft.query(tout[i]+1) - ft.query(tin[i]));
        ll times = ft.query(tout[i]+1) - ft.query(tin[i]);
        ans += min(times * cs1[i], cs2[i]);
    }

    cout << ans << endl;

    
    
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
        
    solve();
   
    
    
    
    
    
    
    
    
    
    
}

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