제출 #407283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407283		soroush	Putovanje (COCI20_putovanje)	C++17	110 / 110	154 ms	21060 KiB

putovanje

//叫んで 藻掻もがいて 瞼まぶたを腫らしても
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 100;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

#define ff first
#define ss second

int n;
vector < pii > adj[maxn];
int a[maxn] , b[maxn] , fen[maxn] , ind[maxn];
int p[maxn] , st[maxn] , ft[maxn] , h[maxn] , head[maxn] , mx[maxn] , sz[maxn] , ti = 0;

void dfs(int v){
	sz[v] = 1 , h[v] = h[p[v]] + 1 , head[v] = v;
	for(auto u : adj[v])if(u.ff ^ p[v])
		ind[u.ff] = u.ss , p[u.ff] = v , dfs(u.ff) , sz[v] += sz[u.ff] , mx[v] = ((sz[mx[v]] <= sz[u.ff]) ? u.ff : mx[v]);
}

void decomp(int v){
	st[v] = ++ti;
	if(mx[v])head[mx[v]] = head[v] , decomp(mx[v]);
	for(auto u : adj[v])if(u.ff ^ p[v] and u.ff ^ mx[v])
		decomp(u.ff);
	ft[v] = ti;
}

int lca(int u , int v){
	while(head[u] ^ head[v]){
		if(h[head[u]] < h[head[v]])swap(u , v);
		u = p[head[u]];
	}
	return ((h[u] < h[v]) ? u : v);
}

void Add(int pos , int x){
	for( ; pos < maxn ; pos += pos & -pos)
		fen[pos] += x;
}

void add(int l , int r){
	if(l > r)return;
	Add(l , 1) , Add(r+1 , -1);
}

int get(int pos){
	int res = 0;
	for( ; pos ; pos -= pos & -pos)
		res += fen[pos];
	return res;
}

void add_path(int u , int v){
	while(head[u] ^ head[v]){
		add(st[head[u]] , st[u]);
		u = p[head[u]];
	}
	add(st[v] + 1 , st[u]);
}

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1 ; i < n ; i ++){
		int u , v;
		cin >> u >> v >> a[i] >> b[i];
		adj[u].pb({v, i});
		adj[v].pb({u, i});
	}
	dfs(1);
	decomp(1);
	for(int i = 1 ; i < n ; i ++){
		int lc = lca(i , i + 1);
		add_path(i , lc);
		add_path(i + 1 , lc);
	}
	ll ans = 0;
	for(int i = 2 ; i <= n ; i ++)
		ans += min(1ll * a[ind[i]] * get(st[i]) , 1ll * b[ind[i]]);
	cout << ans;
	return(0);
}

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