제출 #291254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
291254		mohamedsobhi777	Putovanje (COCI20_putovanje)	C++14	110 / 110	158 ms	26104 KiB

putovanje

#include <bits/stdc++.h>

/*
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")*/

#define I inline void
#define S struct
#define vi vector<ll>
#define vii vector<pair<ll, ll>>

using namespace std;
using ll = long long;
using ld = long double;

const ll N = 1e5 + 7, mod = 1e9 + 7;
const ll inf = 1e16 ; 
// How lleresting!

int n ;

ll ans ; 
vector<pair<int,pair<ll,ll>>> adj[N] ;
int tim ; 
int up[N][20] ; 
int st[N] , en[N] ; 
int cnt[N] ; 

I dfz(int x , int p ){
	st[x] = ++ tim ; 
	up[x][0] = p ;
	for(int i = 1 ;i < 20 ;i++)
		up[x][i] = up[up[x][i-1]][i-1] ; 
	for(auto u : adj[x]){
		if(u.first == p)
			continue ; 
		dfz(u.first , x) ; 
	}
	en[x] = ++ tim ; 
}

bool upper(int u , int v){
	return st[u] <= st[v] && en[v] <= en[u] ; 
}

int dfs(int x , int p){

	int ret = cnt[x]; 
	for(auto u : adj[x]){
		if(u.first == p)
			continue ; 
		int tmp = dfs(u.first , x) ; 
		ans += min(u.second.second , 1ll * u.second.first * tmp) ; 

		ret += tmp ; 
	}	
	return ret ; 
}

int lca(int u , int v){
	if(upper(u , v))
		return u ; 
	if(upper(v , u))
		return v ; 
	for(int i = 19 ; ~i ; -- i){
		if(!upper(up[u][i] , v))
			u = up[u][i] ; 
	}
	return up[u][0] ; 
}

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
       	cin>> n ; 

       	for(int i = 0 ;i < n - 1;i ++){
       		int u , v , c1 , c2 ; 
       		cin >> u >> v >> c1 >> c2 ; 
       		adj[u].push_back({v , {c1 , c2}}) ; 
       		adj[v].push_back({u , {c1 , c2}}) ; 
       	}
       	dfz(1 , 1) ;

       	for(int i = 2 ;i <= n ;i++){
       		int lc = lca(i - 1 , i) ;
       		if(lc == i - 1){
       			cnt[i] ++ ; 
       			cnt[lc] -- ; 
       		}else if(lc == i){
       			cnt[i-1] ++ ; 
       			cnt[lc] -- ; 
       		}
       		else{
       			cnt[i] ++ ; 
       			cnt[i-1] ++ ; 
       			cnt[lc] -= 2; 
       		}
       	}


       	dfs(1 , 1) ; 

       	cout<< ans ; 
	return 0;
}

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