Submission #1273930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273930		SmuggingSpun	Putovanje (COCI20_putovanje)	C++20	110 / 110	71 ms	28600 KiB

putovanje

#include<bits/stdc++.h>
#define taskname "D"
using namespace std;
typedef long long ll;
const int lim = 2e5 + 5;
int n, tdfs = 0, u[lim], v[lim], low[lim], tail[lim], e2v[lim], f[lim], h[lim], c1[lim], c2[lim], up[lim][18];
vector<int>g[lim];
void dfs(int s){
	low[s] = ++tdfs;
	for(int& j : g[s]){
		int d = u[j] ^ v[j] ^ s;
		if(d != up[s][0]){
			e2v[j] = d;
			h[d] = h[up[d][0] = s] + 1;
			for(int i = 1; i < 18; i++){
				up[d][i] = up[up[d][i - 1]][i - 1];
			}
			dfs(d);
		}
	}
	tail[s] = tdfs;
}
int lca(int u, int v){
	if(h[u] < h[v]){
		swap(u, v);
	}
	for(int k = h[u] - h[v], i = 0; i < 18; i++){
		if(k >> i & 1){
			u = up[u][i];
		}
	}
	if(u == v){
		return u;
	}
	for(int i = 17; i > -1; i--){
		if(up[u][i] != up[v][i]){
			u = up[u][i];
			v = up[v][i];
		}
	}
	return up[u][0];
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n;
	for(int i = 1; i < n; i++){
		cin >> u[i] >> v[i] >> c1[i] >> c2[i];
		g[u[i]].push_back(i);
		g[v[i]].push_back(i);
	}
	memset(up, 0, sizeof(up));
	dfs(1);
	memset(f, 0, sizeof(f));
	for(int i = 2; i <= n; i++){
		f[low[i]]++;
		f[low[i - 1]]++;
		f[low[lca(i - 1, i)]] -= 2;
	}
	for(int i = 1; i <= n; i++){
		f[i] += f[i - 1];
	}
	ll ans = 0;
	for(int i = 1; i < n; i++){
		int u = e2v[i];
		ans += min(ll(c2[i]), 1LL * c1[i] * (f[tail[u]] - f[low[u] - 1]));
	}
	cout << ans;
}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:46:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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