제출 #1238632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238632		qrn	Putovanje (COCI20_putovanje)	C++20	110 / 110	221 ms	53384 KiB

putovanje

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

#define SPEED ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long
// #define intt int

const intt mod = 1e9 + 7;
const intt mxN = 4e5 + 5;
const intt inf = 1e18 + 10;
const intt L = 21;

vector<vector<intt>> graph, up;
map<pair<intt,intt>, intt> mp;
vector<pair<intt,intt>> cost;
vector<intt> val(mxN), in(mxN), out(mxN), subsum(mxN);
intt timer;

void dfs(intt node, intt parent) {
	in[node] = timer++;
	up[0][node] = parent;
	for(intt i = 1; i < L; i++) {
		up[i][node] = up[i-1][up[i-1][node]];
	}

	for(auto u : graph[node]) {
		if(u != parent) {
			dfs(u, node);
		}
	}
	out[node] = timer++;
}

bool isata(intt a, intt b) {
	return in[a] <= in[b] && out[a] >= out[b];
}

intt lca(intt a, intt b) {
	if(isata(a, b)) return a;
	if(isata(b, a)) return b;
	for(intt i = L - 1; i >= 0; i--) {
		if(!isata(up[i][a], b)) {
			a = up[i][a];
		}
	}
	return up[0][a];
}

void dfs2(intt node, intt parent) {
	subsum[node] = val[node];
	for(auto u : graph[node]) {
		if(u != parent) {
			dfs2(u, node);
			subsum[node] += subsum[u];
		}
	}
}

vector<intt> choose(mxN);
void dfs3(intt node, intt parent) {
	for(auto u : graph[node]) {
		if(u != parent) {
			dfs3(u, node);
		}
	}

	if(node == parent) return;
	
	intt idx = mp[{min(node, parent), max(node, parent)}];
	intt c1 = cost[idx].fi, c2 = cost[idx].se;
	// cout << "currently: " << min(node, parent) << " " << max(node, parent) << " :: " << c1 << " " << c2 << endl;
	choose[idx] = min(c1 * subsum[node], c2);
}

void solve() {
	intt N;
	cin >> N;
	graph.assign(N + 1, vector<intt> {});
	up.assign(L + 1, vector<intt>(N + 1, 0ll));
	for(intt i = 0; i < N-1; i++) {
		intt a, b, c1, c2;
		cin >> a >> b >> c1 >> c2;
		cost.pb({c1, c2});
		graph[a].pb(b);
		graph[b].pb(a);
		mp[{min(a,b),max(a,b)}] = i;
	}
	dfs(1, 1);

	for(intt i = 1; i < N; i++) {
		intt L = lca(i, i + 1);
		val[i]++; val[i+1]++;
		val[L]-=2;
	}
	dfs2(1, 1);
	dfs3(1, 1);
	intt ans = 0;
	// for(intt i = 1; i <= N; i++) {
	// 	cout << val[i] << " ";
	// }
	// cout << endl;
	// for(intt i = 1; i <= N; i++) {
	// 	cout << subsum[i] << " ";
	// }
	// cout << endl;
	for(intt i = 0; i < N - 1; i++) {
		// cout << choose[i] << " ";
		ans += choose[i];
	}
	// cout << endl;
	cout << ans << endl;
}

signed main() {
	SPEED;
	intt tst = 1;
  	// cin >> tst;
    	while (tst--) {
        	solve();
    	}
}


/*
	p00000
*/

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