Submission #1180444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180444		euthymia2606	Putovanje (COCI20_putovanje)	C++20	110 / 110	70 ms	22200 KiB

putovanje

#include <bits/stdc++.h> 

using namespace std;  

typedef long long ll;  
typedef pair<int, int> ii;  

const int INF = 1e9;  
const ll LINF = 1e18;  

const int N = 2e5 + 5;  

struct AdjEdge {
	int to, id;  
}; 

struct Edge {
	int c1, c2;  
}; 

int n;  
vector<AdjEdge> adj[N];  
vector<Edge> edges; 

int up[18][N]; 
int tin[N], tout[N], timer;   
int edge_to_node[N]; 

void dfs1(int u, int p) {
	tin[u] = ++timer;   
	up[0][u] = p;   
	for (int i = 1; i <= 17; i++) {
		up[i][u] = up[i - 1][up[i - 1][u]]; 
	}
	for (auto e : adj[u]) {
		int v = e.to, id = e.id;
		if (v == p) continue;  
		edge_to_node[id] = v;   
		dfs1(v, u); 
	}
	tout[u] = timer; 
}

bool isAncestor(int u, int v) {
	return (tin[u] <= tin[v] && tout[v] <= tout[u]); 
}

int lca(int u, int v) {
	if (isAncestor(u, v)) return u;  
	if (isAncestor(v, u)) return v;   
	for (int i = 17; i >= 0; i--) {
		if (!isAncestor(up[i][u], v)) {
			u = up[i][u]; 
		}
	}
	return up[0][u]; 
}

int sum[N]; 

void dfs2(int u, int p) {
	for (auto e : adj[u]) {
		int v = e.to; 
		if (v == p) continue; 
		dfs2(v, u);  
		sum[u] += sum[v]; 
	}
}

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); 	
	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, i}); 
		adj[v].push_back({u, i});
		edges.push_back({c1, c2});  
	}

	timer = 0;   
	dfs1(1, 1); 

	for (int u = 1; u + 1 <= n; u++) {
		int v = u + 1;  
		sum[u]++; 
		sum[v]++; 
		sum[lca(u, v)] -= 2;  
	}

	dfs2(1, 1); 

	ll ans = 0;  
	for (int i = 0; i < n - 1; i++) {
		ll c1 = edges[i].c1, c2 = edges[i].c2; 
		int u = edge_to_node[i]; 
		ans += min(sum[u] * c1, c2); 
	}

	cout << ans << '\n'; 
}

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