Submission #500171

#	Time	Username	Problem	Language	Result	Execution time	Memory
500171		inksamurai	Putovanje (COCI20_putovanje)	C++17	110 / 110	180 ms	47008 KiB

putovanje

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define crep(i,x,n) for(ll i=x;i<n;i++)
#define drep(i,n) for(ll i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<ll,ll>;
using vi=vector<ll>;
using vll=vector<long long>;


struct treelca{
	ll n;
	ll timer=0;
	vec(vi) adj;
	vi tin,tout,tour,tourid;
	vi segtree;
	vi depth;
	treelca(ll m,ll root,vec(vi) neadj){
		init(m,root,neadj);
	}
	void init(ll m,ll root,vec(vi) neadj){
		n=m;
		tin.clear();
		tout.clear();
		tour.clear();
		tourid.clear();
		depth.clear();
		tin.resize(n,0);
		tout.resize(n,0);
		tourid.resize(n,0);
		depth.resize(n,0);
		adj=neadj;
		dfs(root,-1);
		segtree.resize(4*sz(tour));
		build(1,0,sz(tour)-1);
	}
	void dfs(ll v,ll par){
		tour.pb(v);
		tourid[v]=sz(tour)-1;
		tin[v]=timer++;
		for(auto u : adj[v]){
			if(u==par) continue;
			depth[u]=depth[v]+1;
			dfs(u,v);
			tour.pb(v);
		}
		tout[v]=timer++;
	}
	void build(ll node,ll l,ll r){
		if(l==r){
			segtree[node]=tour[l];
		}else{
			ll m=(l+r)>>1;
			build(node*2,l,m);
			build(node*2+1,m+1,r);
			segtree[node]=(tin[segtree[node*2]]<tin[segtree[node*2+1]]?segtree[node*2]:segtree[node*2+1]);
		}
	}
	ll query(ll node,ll l,ll r,ll _l,ll _r){
		if(l>_r or r<_l) return -1;
		if(l>=_l and r<=_r) return segtree[node];
		ll m=(l+r)>>1;
		ll vl=query(node*2,l,m,_l,_r);
		ll vr=query(node*2+1,m+1,r,_l,_r);
		if(min(vl,vr)==-1) return max(vl,vr);
		return (tin[vl]<tin[vr]?vl:vr);
	}
	ll ancestor(ll from,ll to){
		ll tinfrom=tin[from],tllo=tin[to];
		if(tinfrom>tllo) swap(tinfrom,tllo);
		return query(1,0,sz(tour)-1,tinfrom,tllo);
	}
	ll dist(ll u,ll v){
		return depth[u]+depth[v]-depth[ancestor(u,v)]*2;
	}
};

int main(){
_3qplfh5;
	ll n;
	cin>>n;
	vec(vec(pii)) adj(n);
	vec(pii) edgecost(n);
	vec(vi) gadj(n);
	rep(i,n-1){
		ll u,v,c1,c2;
		cin>>u>>v>>c1>>c2;
		u--,v--;
		adj[u].pb({v,i});
		adj[v].pb({u,i});
		edgecost[i]={c1,c2};
		gadj[u].pb(v);
		gadj[v].pb(u);
	}
	treelca lca(n,0,gadj);
	vi psum(n,0);
	crep(v,1,n){
		ll up=lca.ancestor(v,v-1);
		psum[up]-=2;
		psum[v]++;
		psum[v-1]++;
	}
	ll ans=0;
	auto magicaldfs=[&](auto self,ll v,ll par)->void{
		for(auto p : adj[v]){
			ll u=p.fi,id=p.se;
			if(u!=par){
				self(self,u,v);
				ans+=min(edgecost[id].fi*psum[u],edgecost[id].se);
				psum[v]+=psum[u];
			}
		}
	};
	magicaldfs(magicaldfs,0,-1);
	cout<<ans<<"\n";
//	
	return 0;
}

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