Submission #282485

#	Time	Username	Problem	Language	Result	Execution time	Memory
282485		AMO5	Putovanje (COCI20_putovanje)	C++17	110 / 110	136 ms	26360 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()  
#define sz(x) int(x.size()) 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=63;
const int mxn=2e5+5;
bool DEBUG=0;

int n;
vector<ii>adj[mxn];
ll c[mxn][2];
int cnt[mxn],cnt2[mxn],par[18][mxn],dep[mxn];

void dfs(int u, int p){
	for(ii x:adj[u]){
		int v=x.fi;
		if(v==p)continue;
		par[0][v]=u;
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
}

int lca(int u, int v){
	if(dep[u]<dep[v])swap(u,v);
	int dif = dep[u]-dep[v];
	for(int i=0; i<18; i++){
		if(dif>>i&1)u=par[i][u];
	}
	if(u==v)return u;
	for(int i=17; i>=0; i--){
		if(par[i][u]!=par[i][v]){
			u=par[i][u];
			v=par[i][v];
		}
	}
	return par[0][u];
}

void dfs2(int u, int p){
	for(ii x:adj[u]){
		int v=x.fi;
		int ind=x.se;
		if(v==p)continue;
		dfs2(v,u);
		cnt2[ind]=cnt[v];
		cnt[u]+=cnt[v];
	}
}

void solve(int u, int v){
	int LCA = lca(u,v);
	cnt[u]++;
	cnt[v]++;
	cnt[LCA]-=2;
	/*
	cerr<<u<<" "<<LCA<<": \n";
	for(int i=1; i<=n; i++){
		cerr<<i<<" "<<cnt[i]<<"\n";
	}
	*/ 
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    cin>>n;
    for(int i=0; i<n-1; i++){
		int u,v; 
		cin>>u>>v>>c[i][0]>>c[i][1];
		adj[u].eb(v,i);
		adj[v].eb(u,i);
	}
	dep[1]=1;
	dfs(1,0);
	for(int i=1; i<18; i++){
		for(int j=1; j<=n; j++){
			if(par[i-1][j]){
				par[i][j]=par[i-1][par[i-1][j]];
			}
		}
	}
	for(int i=1; i<=n-1; i++)solve(i,i+1);
	/*
	int LCA = lca(n,1);
	cnt[n]--; cnt[1]--;
	cnt[LCA]+=2;
	
	for(int i=1; i<=n; i++){
		cerr<<i<<" "<<cnt[i]<<"\n";
	}
	*/
	dfs2(1,0);
	/*
	for(int i=1; i<=n; i++){
		cerr<<i<<" "<<cnt[i]<<"\n";
	}
	*/ 
	ll ans=0ll;
	for(int i=0; i<n-1; i++){
		if(cnt2[i]){
			ll p1=1ll*cnt2[i]*c[i][0];
			if(p1<=c[i][1]){
				ans+=p1;
			}else{
				ans+=c[i][1];
			}
		}
	}
	cout<<ans;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

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