Submission #1137096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137096		shiro	Putovanje (COCI20_putovanje)	C++20	110 / 110	100 ms	36932 KiB

putovanje

#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <string>
#include <set>
#include <functional>
#include <complex>
#include <queue>
#include <random>
#include <chrono>
#include <unordered_map>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,tune=native")
typedef long double ld;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pp = std::pair<ll, ll>;
using mll = std::map<ll, ll>;
using cd = std::complex<double>;
using unm = std::unordered_map<ll, ll>;
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define yes cout << "YES" << '\n'
#define no cout << "NO" << '\n'
#define DDD ll gcd(ll a, ll b) { while (b) b ^= a ^= b ^= a %= b; return a; }
#define RRR mt19937 rand_(chrono::steady_clock::now().time_since_epoch().count()); ll randll() { return uniform_int_distribution<ll>()(rand_); }
using namespace std;
struct road {
	ll to, c1, c2;
};
ll n, ans = 0;
vector<road> g[200005];
ll tin[200005], tout[200005], depth[200005], t = 1, Z[200005][20], par[200005], c1[200005], c2[200005], cnt[200005];
void ZZZ(ll node = 1, ll pr = 1, ll dep = 1) {
	par[node] = pr;
	depth[node] = dep;
	tin[node] = t; t++;
	Z[node][0] = pr;
	for (ll st = 1; st < 20; st++) {
		Z[node][st] = Z[Z[node][st - 1]][st - 1];
	}

	for (road x : g[node]) {
		if (x.to != pr) {
			c1[x.to] = x.c1;
			c2[x.to] = x.c2;
			ZZZ(x.to, node, dep + 1);
		}
	}

	tout[node] = t; t++;
}

ll lca(ll v, ll u) {
	for (ll st = 19; v != u;) {
		if (depth[v] < depth[u])swap(v, u);
		if (tin[Z[v][st]] <= tin[u] && tout[u] <= tout[Z[v][st]] && st != 0) st--;
		else 
			v = Z[v][st];
	}
	return v;
}

void ADD(ll v, ll u) {
	ll w = lca(v, u);
	cnt[v]++;
	cnt[u]++;
	cnt[w]--;
	cnt[w]--;
}

void fill_cnt(ll node = 1) {
	ll lnr = cnt[node];
	for (road x : g[node]) {
		if (x.to != par[node]) {
			fill_cnt(x.to);
			lnr += cnt[x.to];
		}
	}
	cnt[node] = lnr;
	ans += min(c2[node], c1[node] * lnr);
}

int main() {
	speed;
	cin >> n;
	for (ll i = 1; i < n; i++) {
		ll a, b, c1, c2;
		cin >> a >> b >> c1 >> c2;
		g[a].push_back({ b, c1, c2 });
		g[b].push_back({ a, c1, c2 });
	}
	ZZZ();
	for (ll i = 1; i < n; i++) {
		ADD(i, i + 1);
	}
	fill_cnt();
	cout << ans << endl;
}

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