Submission #1102136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102136		quocthang	Putovanje (COCI20_putovanje)	C++14	110 / 110	129 ms	39756 KiB

putovanje

#include <bits/stdc++.h>
#define base 31
#define fi first
#define endl "\n"
#define se second
#define NAME "FILE"
#define ll long long
#define int long long
#define mod 1000000007
#define pii pair<int,int>
#define bit(mask,i) (mask&(1<<i))
#define lcm(a,b) ((a*b)/__gcd(a,b))
#define turn_on(mask,i) (mask|(1<<i))
#define turn_off(mask,i) (mask^(1<<i))

template <class T1, class T2>
bool maximize(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;}

template <class T1, class T2>
bool minimize(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;}

template <class T1, class T2>
void add(T1 &a, T2 b){a += b; if (a >= mod) a -= mod;}

template <class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if (a < 0) a += mod;}

using namespace std;
struct LCA{
	int pa[200010][20],d[2000010];
	struct Data{
		int v,cost_1,cost_2;
	};
	vector<Data>adj[200010];
	void ADD(int u,int v,int cost_1,int cost_2){
		adj[u].push_back({v,cost_1,cost_2});
		adj[v].push_back({u,cost_1,cost_2});
	}
	void dfs(int u,int p){
		for(auto x:adj[u]){
			int v=x.v;
			if(v==p)continue;
			d[v]=d[u]+1;
			pa[v][0]=u;
			for(int i=1;i<=18;i++)pa[v][i]=pa[pa[v][i-1]][i-1];
			dfs(v,u);
		}
	}
	int get(int u,int v){
		if(d[u]!=d[v]){
			if(d[u]<d[v])swap(u,v);
			int k=d[u]-d[v];
			for(int i=0;(1<<i)<=k;i++)
				if(bit(k,i)) u=pa[u][i];
		}
		if(u==v)return u;
		int k=__lg(d[u]);
		for(int i=k;i>=0;i--){
			if(pa[u][i]!=pa[v][i])
				u=pa[u][i],
				v=pa[v][i];
		}
		return pa[u][0];
	}
}lca;
int n;
int d[200010];
void dfs(int u,int p){
	for(auto x:lca.adj[u]){
		int v=x.v;
		if(v==p)continue;
		dfs(v,u);
		d[u]+=d[v];
	}
}
int ans=0;
void calc(int u,int p){
	for(auto x:lca.adj[u]){
		int v=x.v,cost_1=x.cost_1,cost_2=x.cost_2;
		if(v==p)continue;
		ans+=min(d[v]*cost_1,cost_2);
		calc(v,u);
	}
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	if (fopen(NAME".inp","r")){
		freopen(NAME".inp","r",stdin);
		freopen(NAME".out","w",stdout);
	}
	cin>>n;	
	for(int i=1,u,v,cost_1,cost_2;i<n;i++){
		cin>>u>>v>>cost_1>>cost_2;
		lca.ADD(u,v,cost_1,cost_2);
	}
	lca.dfs(1,0);
	for(int i=1;i<n;i++){
		d[i]++;
		d[i+1]++;
		d[lca.get(i,i+1)]-=2;
	}
	dfs(1,0);
	calc(1,0);
	cout<<ans;
}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:89:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   freopen(NAME".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:90:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   freopen(NAME".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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