Submission #839489

#	Time	Username	Problem	Language	Result	Execution time	Memory
839489		serifefedartar	Putovanje (COCI20_putovanje)	C++17	20 / 110	75 ms	23104 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) {cout << #x << ": "; for (auto it : x) cout << it << " ";cout << endl;}
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 998244353
#define LOGN 20
#define MAXN 200005

vector<vector<pair<int,pair<int,int>>>> graph;
vector<ll> cnt;
int up[LOGN][MAXN], depth[MAXN];
void dfs(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		depth[u.f] = depth[node] + 1;
		up[0][u.f] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u.f] = up[i-1][up[i-1][u.f]];
		dfs(u.f, node);
	}
}

int find(int node, int k) {
	for (int i = 0; i < LOGN; i++) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}

int lca(int a, int b) {
	if (depth[b] > depth[a])
		swap(a, b);
	a = find(a, depth[a] - depth[b]);
	if (a == b)
		return a;

	for (int i = LOGN-1; i >= 0; i--) {
		if (up[i][a] != up[i][b]) {
			a = up[i][a];
			b = up[i][b]; 
		}
	}
	return up[0][a];
}

ll ans = 0;
int dfs2(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		int Q = dfs2(u.f, node);
		ans += min(u.s.f * Q, u.s.s);
		cnt[node] += Q;
	}
	return cnt[node];
}

int main() {
	fast
	int N;
	cin >> N;

	graph = vector<vector<pair<int,pair<int,int>>>>(N+1, vector<pair<int,pair<int,int>>>());
	cnt = vector<ll>(N+1, 0); 
	for (int i = 1; i < N; i++) {
		int A, B, C1, C2; 
		cin >> A >> B >> C1 >> C2;
		graph[A].push_back({B, {C1, C2}}); 
		graph[B].push_back({A, {C1, C2}}); 
	}
	for (int i = 0; i < LOGN; i++)
		up[i][1] = 1; 
	dfs(1, 1);

	for (int i = 1; i <= N-1; i++) {
		int Q = lca(i, i+1); 
		cnt[i]++;
		cnt[i+1]++;
		cnt[Q]-=2;
	}
	dfs2(1, 1);

	cout << ans << "\n"; 
}

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