Submission #813106

#	Time	Username	Problem	Language	Result	Execution time	Memory
813106		vjudge1	Putovanje (COCI20_putovanje)	C++17	110 / 110	114 ms	36604 KiB

putovanje

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

#define int long long
#define pb push_back
#define debug(x) cout << #x << ": " << (x) << endl
#define eb emplace_back
#define all(x) (x).begin(), (x).end()

typedef long long ll;

const int mxN = 2e5+5;
const int mxM = 2e5+5;
const int logN = 20;


vector<pair<int, int>> g[mxN];
int tin[mxN];
int tout[mxN];
int up[mxN][logN];


int dfstime = 0;

void dfs(int a, int p)
{
	tin[a] = dfstime++;
	up[a][0] = p;
	for (int j = 1; j < logN; j++) {
		up[a][j] = up[ up[a][j-1] ][j-1];
	}
	for (auto [b, idx]: g[a]) {
		if (b == p) continue;
		dfs(b, a);
	}
	tout[a] = dfstime;
}

bool is_ancestor(int a, int b)
{
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int psum[mxN];

int get_lca(int a, int b)
{
	if (is_ancestor(a, b)) {
		return a;
	} 
	if (is_ancestor(b, a)) {
		return b;
	}
	for (int j = logN -1; j >= 0; j--) {
		if (!is_ancestor(up[a][j], b)) {
			a = up[a][j];
		}
	}
	return up[a][0];
}

int single[mxM];
int multi[mxM];
int used[mxM];

int dfs2(int a, int p) {
	int ans = 0;
	for (auto [b, idx]: g[a]) {
		if (b == p) continue;
		int t = dfs2(b, a);
		used[idx] = t;
		ans += t;
	}
	return ans + psum[a];
}


void solve()
{
	int n;
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int a, b, s, m;
		cin >> a >> b >> s >> m;
		a--; b--;
		single[i] = s;
		multi[i] = m;
		g[a].pb({b, i});
		g[b].pb({a, i});
	}
	dfs(0, 0);
	for (int a = 0; a < n-1; a++) {
		int b = a + 1;
		int lca = get_lca(a, b);
		psum[a]++;
		psum[b]++;
		psum[lca] -= 2;
	}
	dfs2(0, 0);
	int ans = 0;
	for (int i = 0; i < n-1; i++) {
		ans += min(multi[i], used[i]*single[i]);
	}
	cout << ans << endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;
	// cin >> t;
	while(t--) solve();
	return 0;
}

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