Submission #208574

#	Time	Username	Problem	Language	Result	Execution time	Memory
208574		jurichhh8	Putovanje (COCI20_putovanje)	C++14	110 / 110	315 ms	44280 KiB

putovanje

#include <iostream>
#include <cmath>
#include <vector>
#include <utility>

using namespace std;

#define f first
#define s second
#define mp make_pair

int pred[21][200003],height[200003],parent[200003],n;
long long dp[21][200003];
vector<pair<int,pair<long long,long long> > > veki[200003];
pair<long long,long long> cijena[200003];

void dfs(int x,int p){
	height[x]=height[p]+1;
	parent[x]=p;
	for(int i=0;i<veki[x].size();i++){
		if(veki[x][i].f==p){
			cijena[x]=veki[x][i].s;
			continue;
		}
		dfs(veki[x][i].f,x);
	}
}
void prep(){
	for(int i=1;i<=n;i++){
		pred[0][i]=parent[i];
	}
	for(int i=1;i<21;i++){
		for(int j=1;j<=n;j++){
			pred[i][j]=pred[i-1][pred[i-1][j]];
		}
	}
}
int getanc(int x,int v){
	if(v==0) return x;
	for(int i=0;i<21;i++){
		if(v&(1<<i)){
			dp[i][x]++;
			x=pred[i][x];
		}
	}
	return x;
}
void lca(int x,int y){
	if(height[y]>height[x]) swap(x,y);
	x=getanc(x,height[x]-height[y]);
	if(x==y) return;
	for(int i=20;i>=0;i--){
		if(pred[i][x]==pred[i][y]) continue;
		dp[i][x]++;
		dp[i][y]++;
		x=pred[i][x];
		y=pred[i][y];
	}
	dp[0][x]++;
	dp[0][y]++;
}

int main () {
	cin>>n;
	for(int i=0;i<n-1;i++){
		long long c1,c2;
		int a,b;
		cin>>a>>b>>c1>>c2;
		veki[a].push_back(mp(b,mp(c1,c2)));
		veki[b].push_back(mp(a,mp(c1,c2)));
	}
	dfs(1,0);
	prep();
	for(int i=1;i<n;i++){
		lca(i,i+1);
	}
	for(int i=20;i>0;i--){
		for(int j=1;j<=n;j++){
			dp[i-1][j]+=dp[i][j];
			dp[i-1][pred[i-1][j]]+=dp[i][j];
		}
	}
	long long sol=0;
	for(int i=2;i<=n;i++){
		sol+=min(dp[0][i]*cijena[i].f,cijena[i].s);
	}
	cout<<sol;



return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'void dfs(int, int)':
putovanje.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<veki[x].size();i++){
              ~^~~~~~~~~~~~~~~

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