Submission #440786

#	Time	Username	Problem	Language	Result	Execution time	Memory
440786		Tahmid690	Putovanje (COCI20_putovanje)	C++14	110 / 110	677 ms	74652 KiB

putovanje

// "Say:He is the Most Merciful,We have believed in him and upon him we have relied" [67:29]
 
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
//#pragma GCC optimize("unroll-loops")
 
#include<bits/stdc++.h>
using namespace std;
                                                     
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 */
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef map<int,int> mpi;
typedef map<ll,ll> mpl;
typedef unordered_map<int,int> umpi;
typedef unordered_map<ll,ll> umpl;
 
#define ump unordered_map
#define mod 1000000007
#define inf 1000000000000000006
#define infi 1000000009
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
#define pi acos(-1.0)
#define dec(n) fixed << setprecision(n)
#define N 200005
#define int long long

inline void IO(string name) { // Usaco
     freopen((name + ".in").c_str(), "r", stdin);
     freopen((name + ".out").c_str(), "w", stdout);
}

struct edge{
	int u,v,c1,c2;
};



int n,par[N],con[N],lvl[N];
vector<edge> e;
vii g[N];
map<pii,int> mp;

struct lca{
	int anc[N][25];
	void init(int par[],int n){
		memset(anc,-1,sizeof anc);
		for(int i=1;i<=n;i++) anc[i][0]=par[i];
		for(int j=1;(1<<j)<n;j++){
			for(int i=1;i<=n;i++){
				if(anc[i][j-1]!=-1) anc[i][j]=anc[anc[i][j-1]][j-1];
			}
		}
	}
	int findlca(int p,int q,int n){
		int log;
        if (lvl[p]<lvl[q]) swap(p,q);
        log=1;
    	while(1){
        	int nxt=log+1;
        	if((1<<nxt)>lvl[p])break;
        	log++;
    	}
        for(int i=log;i>=0;i--) if(lvl[p]-(1<<i)>=lvl[q]) p=anc[p][i];
    	if(p==q) return p;
        for (int i=log;i>=0;i--){
        	if(anc[p][i]!=-1 && anc[p][i]!=anc[q][i]) p=anc[p][i],q=anc[q][i];
        }
      return par[p];
	}
}khela;


void mdfs(int s,int p){
	par[s]=p;
	lvl[s]=lvl[p]+1;
	for(auto dd:g[s]){
		if(dd==p) continue;
		mdfs(dd,s);
	}
}

ll dfs(int s,int p){
	ll val=0;
	for(auto dd:g[s]){
		if(dd==p) continue;
		ll momo=dfs(dd,s);
		mp[{s,dd}]+=momo;
		mp[{dd,s}]+=momo;
		val+=momo;
	}
	return val+con[s];
}
void solve(){
	cin >> n;
	e.resize(n-1);
	for(int i=0;i<n-1;i++){
		cin >> e[i].u >> e[i].v >> e[i].c1 >> e[i].c2;
		g[e[i].u].pb(e[i].v);
		g[e[i].v].pb(e[i].u);
	}
	lvl[0]=-1;
	mdfs(1,0);
	khela.init(par,n);
	for(int i=1;i<n;i++){
		con[i]++;
		con[i+1]++;
		con[khela.findlca(i,i+1,n)]-=2;
	}
	
	int xxx=dfs(1,0);
	ll cost=0;
	for(edge xx:e){
		ll cnt=mp[{xx.u,xx.v}];
		cost+=min(cnt*xx.c1,xx.c2);
	}
	cout << cost << endl;
	
}

signed main(){
    fastio;
    //srand(chrono::steady_clock::now().time_since_epoch().count());
    int T=1,cs=0;
    //cin >> T;
	
    while(T--){
        //cout << "Case " << ++cs << ":" << " " ; 
    	solve();
    } 
}

Compilation message (stderr)

putovanje.cpp: In function 'void solve()':
putovanje.cpp:127:6: warning: unused variable 'xxx' [-Wunused-variable]
  127 |  int xxx=dfs(1,0);
      |      ^~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:140:13: warning: unused variable 'cs' [-Wunused-variable]
  140 |     int T=1,cs=0;
      |             ^~

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