oj.uz

Submission #839489

# Submission time Handle Problem Language Result Execution time Memory
839489 2023-08-30T07:06:48 Z serifefedartar Putovanje (COCI20_putovanje) C++17
20 / 110
 75 ms 23104 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) {cout << #x << ": "; for (auto it : x) cout << it << " ";cout << endl;}
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 998244353
#define LOGN 20
#define MAXN 200005

vector<vector<pair<int,pair<int,int>>>> graph;
vector<ll> cnt;
int up[LOGN][MAXN], depth[MAXN];
void dfs(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		depth[u.f] = depth[node] + 1;
		up[0][u.f] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u.f] = up[i-1][up[i-1][u.f]];
		dfs(u.f, node);
	}
}

int find(int node, int k) {
	for (int i = 0; i < LOGN; i++) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}

int lca(int a, int b) {
	if (depth[b] > depth[a])
		swap(a, b);
	a = find(a, depth[a] - depth[b]);
	if (a == b)
		return a;

	for (int i = LOGN-1; i >= 0; i--) {
		if (up[i][a] != up[i][b]) {
			a = up[i][a];
			b = up[i][b]; 
		}
	}
	return up[0][a];
}

ll ans = 0;
int dfs2(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		int Q = dfs2(u.f, node);
		ans += min(u.s.f * Q, u.s.s);
		cnt[node] += Q;
	}
	return cnt[node];
}

int main() {
	fast
	int N;
	cin >> N;

	graph = vector<vector<pair<int,pair<int,int>>>>(N+1, vector<pair<int,pair<int,int>>>());
	cnt = vector<ll>(N+1, 0); 
	for (int i = 1; i < N; i++) {
		int A, B, C1, C2; 
		cin >> A >> B >> C1 >> C2;
		graph[A].push_back({B, {C1, C2}}); 
		graph[B].push_back({A, {C1, C2}}); 
	}
	for (int i = 0; i < LOGN; i++)
		up[i][1] = 1; 
	dfs(1, 1);

	for (int i = 1; i <= N-1; i++) {
		int Q = lca(i, i+1); 
		cnt[i]++;
		cnt[i+1]++;
		cnt[Q]-=2;
	}
	dfs2(1, 1);

	cout << ans << "\n"; 
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 688 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 708 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 672 KB Output is correct
9 Correct 2 ms 692 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 19148 KB Output is correct
2 Correct 72 ms 20540 KB Output is correct
3 Incorrect 75 ms 23104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 688 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 708 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 672 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 70 ms 19148 KB Output is correct
11 Correct 72 ms 20540 KB Output is correct
12 Incorrect 75 ms 23104 KB Output isn't correct
13 Halted 0 ms 0 KB -