제출 #1272250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272250		nhq0914	Putovanje (COCI20_putovanje)	C++17	110 / 110	86 ms	22128 KiB

putovanje

#include <bits/stdc++.h>
#define vpii vector <pair <int, int>>
using namespace std;
using ll = int64_t;
const int N = 2e5 + 1, Log = 18;
int n;
int h[N];
int par[N][Log];
int price[N][2];
int rtail[N];
ll dif[N], ans;
vpii g[N];
void dfs(int v){
	for(pair <int, int> &x: g[v]) if(x.first != par[v][0]){
		int &u = x.first;
		par[u][0] = v;
		h[u] = h[v] + 1;
		rtail[u] = x.second;
		for(int i = 1; i < Log; ++i)
			par[u][i] = par[par[u][i - 1]][i - 1];
		dfs(u);
	}
}
int getlca(int u, int v){
	int dif = h[u] - h[v];
	if(dif < 0){
		dif = -dif;
		u ^= v ^= u ^= v;
	}
	for(int i = 0; i < Log; ++i) if(dif >> i & 1) u = par[u][i];
	if(u == v) return u;
	for(int i = Log - 1; ~i; --i) if(par[u][i] != par[v][i])
		u = par[u][i], v = par[v][i];
	return par[u][0];
}
void dfssolve(int v){
	for(pair <int, int> &x: g[v]) if(x.first != par[v][0]){
		dfssolve(x.first);
		dif[v] += dif[x.first];
	}
	if(v != 1)
		ans += min(price[rtail[v]][0] * dif[v], (ll) price[rtail[v]][1]);
}
int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n;
	for(int u, v, i = 1; i < n; ++i){
		cin >> u >> v >> price[i][0] >> price[i][1];
		g[u].push_back({v, i});
		g[v].push_back({u, i});
	}
	dfs(1);
	for(int lca, u, v, i = 2; i <= n; ++i){
		lca = getlca(i - 1, i);
		u = i - 1, v = i;
		if(h[u] > h[v]) u ^= v ^= u ^= v;
		if(lca == u){
			++dif[v];
			--dif[u];
		}else{
			++dif[u]; ++dif[v];
			dif[lca] -= 2;
		}
	}
	dfssolve(1);
	cout << ans;
	cerr << "ok\n";
	return 0;
}

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