Submission #291570

#	Time	Username	Problem	Language	Result	Execution time	Memory
291570		penguinhacker	Putovanje (COCI20_putovanje)	C++17	110 / 110	182 ms	22136 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
int n, c1[mxN], c2[mxN], dep[mxN], anc[mxN][18];
vector<ar<int, 3>> adj[mxN];

void dfs1(int u=0, int p=-1) {
	for (int i=1; i<18; ++i) anc[u][i]=anc[anc[u][i-1]][i-1];
	for (auto& v : adj[u]) if (v[0]!=p) {
		c1[v[0]]=v[1];
		c2[v[0]]=v[2];
		dep[v[0]]=dep[u]+1;
		anc[v[0]][0]=u;
		dfs1(v[0], u);
	}
}

int lca(int a, int b) {
	if (dep[a]>dep[b]) swap(a, b);
	for (int i=17; ~i; --i) if (dep[b]-(1<<i)>=dep[a]) b=anc[b][i];
	if (a==b) return a;
	for (int i=17; ~i; --i) if (anc[a][i]!=anc[b][i]) a=anc[a][i], b=anc[b][i];
	return anc[a][0];
}

int cnt[mxN];
void dfs2(int u=0, int p=-1) {
	for (auto& v : adj[u]) if (v[0]!=p) {
		dfs2(v[0], u);
		cnt[u]+=cnt[v[0]];
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i=1; i<n; ++i) {
		int a, b, c, d; cin >> a >> b >> c >> d, --a, --b;
		adj[a].push_back({b, c, d});
		adj[b].push_back({a, c, d});
	}
	dfs1();
	for (int i=1; i<n; ++i) {
		++cnt[i], ++cnt[i-1];
		cnt[lca(i, i-1)]-=2;
	}
	dfs2();
	ll ans=0;
	for (int i=1; i<n; ++i) ans+=min((ll)cnt[i]*c1[i], (ll)c2[i]);
	cout << ans << "\n";
	return 0;
}

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