oj.uz

Submission #653724

# Submission time Handle Problem Language Result Execution time Memory
653724 2022-10-27T19:44:00 Z Koful123 Putovanje (COCI20_putovanje) C++17
110 / 110
 158 ms 39640 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define pb push_back
#define ff first
#define ss second
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const int N = 2e5 + 5;
int n;
vector<int> cnt(N),sum(N),vis(N),depth(N);
vector<pair<int,int>> adj[N],val(N);
int par[N][20];

void dfs(int node,int p){
	for(auto[go,who] : adj[node]){
		if(go == p) continue;
		dfs(go,node);
	}
	for(auto[go,who] : adj[node]){
		if(go == p) continue;
		cnt[who] = sum[go],sum[node] += sum[go];
	}
}

void find(int node,int p){
	par[node][0] = p,depth[node] = depth[p] + 1;
	for(auto[go,who] : adj[node]){
		if(go == p) continue;
		find(go,node);
	}
}

int lca(int x,int y){
	if(depth[x] < depth[y]) swap(x,y);
	int d = depth[x] - depth[y];
	for(int i=19;i>=0;i--){
		if(d & 1ll<<i){
			x = par[x][i];
		}
	}
	if(x == y) return x;
	for(int i=19;i>=0;i--){
		if(par[x][i] != par[y][i]){
			x = par[x][i],y = par[y][i];
		}
	}
	return par[x][0];
}

void solve(){

	cin >> n;
	for(int i=1;i<n;i++){
		int a,b; cin >> a >> b >> val[i].ff >> val[i].ss;
		adj[a].pb({b,i});
		adj[b].pb({a,i});
	}

	find(1,0);
	for(int i=1;i<20;i++){
		for(int j=1;j<=n;j++){
			par[j][i] = par[par[j][i-1]][i-1];
		}
	}

	for(int i=1;i<n;i++){
		int get = lca(i,i+1);
		sum[get] -= 2,sum[i]++,sum[i+1]++;
	}

	dfs(1,0);
	
	int ans = 0;
	for(int i=1;i<n;i++){
		ans += min(cnt[i] * val[i].ff,val[i].ss);
	}

	cout << ans << endl;
}	

signed main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	int t = 1;
//	cin >> t;

	while(t--)
		solve();

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14804 KB Output is correct
3 Correct 9 ms 14832 KB Output is correct
4 Correct 8 ms 14836 KB Output is correct
5 Correct 8 ms 14832 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 7 ms 14480 KB Output is correct
8 Correct 8 ms 14676 KB Output is correct
9 Correct 8 ms 14804 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 35080 KB Output is correct
2 Correct 121 ms 35844 KB Output is correct
3 Correct 151 ms 37848 KB Output is correct
4 Correct 158 ms 38128 KB Output is correct
5 Correct 7 ms 14548 KB Output is correct
6 Correct 129 ms 34564 KB Output is correct
7 Correct 86 ms 28900 KB Output is correct
8 Correct 156 ms 36804 KB Output is correct
9 Correct 86 ms 38092 KB Output is correct
10 Correct 78 ms 37424 KB Output is correct
11 Correct 88 ms 39396 KB Output is correct
12 Correct 92 ms 39640 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14804 KB Output is correct
3 Correct 9 ms 14832 KB Output is correct
4 Correct 8 ms 14836 KB Output is correct
5 Correct 8 ms 14832 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 7 ms 14480 KB Output is correct
8 Correct 8 ms 14676 KB Output is correct
9 Correct 8 ms 14804 KB Output is correct
10 Correct 143 ms 35080 KB Output is correct
11 Correct 121 ms 35844 KB Output is correct
12 Correct 151 ms 37848 KB Output is correct
13 Correct 158 ms 38128 KB Output is correct
14 Correct 7 ms 14548 KB Output is correct
15 Correct 129 ms 34564 KB Output is correct
16 Correct 86 ms 28900 KB Output is correct
17 Correct 156 ms 36804 KB Output is correct
18 Correct 86 ms 38092 KB Output is correct
19 Correct 78 ms 37424 KB Output is correct
20 Correct 88 ms 39396 KB Output is correct
21 Correct 92 ms 39640 KB Output is correct
22 Correct 121 ms 36460 KB Output is correct
23 Correct 91 ms 33908 KB Output is correct
24 Correct 138 ms 36080 KB Output is correct
25 Correct 8 ms 14548 KB Output is correct
26 Correct 50 ms 24244 KB Output is correct
27 Correct 101 ms 33100 KB Output is correct
28 Correct 77 ms 35304 KB Output is correct
29 Correct 96 ms 39616 KB Output is correct
30 Correct 91 ms 39124 KB Output is correct
31 Correct 8 ms 14676 KB Output is correct