Submission #224199

#	Time	Username	Problem	Language	Result	Execution time	Memory
224199		jamielim	Putovanje (COCI20_putovanje)	C++14	110 / 110	172 ms	36340 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

const int MAXN = 200100;
int n;
struct UnionFind {
	vector <int> v[MAXN];
	int connected[MAXN],par[MAXN];
	void init() {
		for(int i=0;i<MAXN;i++){
			v[i].clear();v[i].push_back(i);
			par[i]=i;
			connected[i]=0;
		}
	}
	void merge(int a, int b) {
		a = par[a];b = par[b];
		if ((int)v[a].size() < (int)v[b].size()) swap(a, b); //merging smaller into larger
		for (auto x : v[b]) {
			if (par[x - 1] == a) connected[a]++;
			if (par[x + 1] == a) connected[a]++;
			v[a].push_back(x);
		}
		for (auto x : v[b]) par[x] = a;
		connected[a] += connected[b];
	}
	int get(int x) { //number of times the edge from x to its parent (original tree) is used
		x = par[x];
		int ret = ((int)v[x].size() - connected[x]) * 2;
		if (par[1] == x) ret--;
		if (par[n] == x) ret--;
		return ret;
	}
}Uf;
int c[MAXN],d[MAXN],cnt[MAXN];
vector<pii> adj[MAXN];
void dfs(int x,int p,int idx){
	for(int i=0;i<(int)adj[x].size();i++){
		if(adj[x][i].first==p)continue;
		dfs(adj[x][i].first,x,adj[x][i].second);
		Uf.merge(x,adj[x][i].first);
	}
	if(idx!=-1)cnt[idx]=Uf.get(x);
}

int main(){
	scanf("%d",&n);
	int a,b;
	for(int i=0;i<n-1;i++){
		scanf("%d%d%d%d",&a,&b,&c[i],&d[i]);
		adj[a].push_back(make_pair(b,i));adj[b].push_back(make_pair(a,i));
	}
	Uf.init();
	dfs(1,-1,-1);
	ll ans=0;
	for(int i=0;i<n-1;i++)ans+=min((ll)c[i]*(ll)cnt[i],(ll)d[i]);
	printf("%lld",ans);
}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
putovanje.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&a,&b,&c[i],&d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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