oj.uz

Submission #637455

# Submission time Handle Problem Language Result Execution time Memory
637455 2022-09-01T20:28:04 Z vovamr Putovanje (COCI20_putovanje) C++17
110 / 110
 134 ms 20240 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 2e5 + 10;
ve<int> gr[N];
int in[N], out[N];
const int lg = 18;
int up[N][lg];

int timer = 0;
inline void dfs(int v, int p) {
	in[v] = timer++; up[v][0] = p;
	for (int i = 1; i < lg; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto &to : gr[v]) if (to ^ p) dfs(to, v);
	out[v] = timer++;
}
inline bool anc(int a, int b) { return in[a] <= in[b] && out[b] <= out[a]; }
inline int lca(int a, int b) {
	if (anc(a, b)) return a;
	if (anc(b, a)) return b;
	for (int i = lg - 1; ~i; --i) {
		if (!anc(up[a][i], b)) {
			a = up[a][i];
		}
	} return up[a][0];
}

int s[N];
inline void add(int a, int b) {
	int l = lca(a, b);
	++s[a], ++s[b], ----s[l];
}
inline void dfs1(int v, int p) {
	for (auto &to : gr[v]) if (to ^ p) {
		dfs1(to, v);
		s[v] += s[to];
	}
}

inline void solve() {
	int n;
	cin >> n;
	ve<array<int,4>> e(n - 1);
	for (int i = 1; i < n; ++i) {
		int v, u, a, b;
		cin >> v >> u >> a >> b;
		e[i - 1] = {--v, --u, a, b};

		gr[v].pb(u), gr[u].pb(v);
	}

	dfs(0, 0);
	for (int i = 0; i + 1 < n; ++i) add(i, i + 1);
	dfs1(0, 0);

	ll ans = 0;
	for (auto &[v, u, a, b] : e) {
		if (in[v] < in[u]) swap(v, u);
		ans += min(a * 1ll * s[v], b * 1ll);
	}

	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 6 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 6 ms 5204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 18060 KB Output is correct
2 Correct 117 ms 18752 KB Output is correct
3 Correct 125 ms 20020 KB Output is correct
4 Correct 109 ms 20240 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 101 ms 17772 KB Output is correct
7 Correct 68 ms 14312 KB Output is correct
8 Correct 134 ms 18132 KB Output is correct
9 Correct 90 ms 18888 KB Output is correct
10 Correct 90 ms 18448 KB Output is correct
11 Correct 75 ms 19508 KB Output is correct
12 Correct 76 ms 19600 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 6 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 6 ms 5204 KB Output is correct
10 Correct 127 ms 18060 KB Output is correct
11 Correct 117 ms 18752 KB Output is correct
12 Correct 125 ms 20020 KB Output is correct
13 Correct 109 ms 20240 KB Output is correct
14 Correct 5 ms 5076 KB Output is correct
15 Correct 101 ms 17772 KB Output is correct
16 Correct 68 ms 14312 KB Output is correct
17 Correct 134 ms 18132 KB Output is correct
18 Correct 90 ms 18888 KB Output is correct
19 Correct 90 ms 18448 KB Output is correct
20 Correct 75 ms 19508 KB Output is correct
21 Correct 76 ms 19600 KB Output is correct
22 Correct 126 ms 17456 KB Output is correct
23 Correct 111 ms 16004 KB Output is correct
24 Correct 129 ms 17324 KB Output is correct
25 Correct 4 ms 5192 KB Output is correct
26 Correct 42 ms 10704 KB Output is correct
27 Correct 90 ms 15504 KB Output is correct
28 Correct 63 ms 17304 KB Output is correct
29 Correct 90 ms 19588 KB Output is correct
30 Correct 96 ms 19412 KB Output is correct
31 Correct 5 ms 5204 KB Output is correct