Submission #945636

#	Time	Username	Problem	Language	Result	Execution time	Memory
945636		phamducminh	Putovanje (COCI20_putovanje)	C++17	110 / 110	175 ms	61524 KiB

putovanje

//******************/
//*   I<3   C++    */
//*  I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S INTERESTING*/
//* I LOVE PROGRAM!*/
//*  IN CONTESTS   */
//*   GET SCORE    */
//*    AC CODE     */
//*     LET'S      */
//*      GO        */
//*  Written by:   */
//*   Duc Minh     */






#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME        (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a)      a.begin(),a.end()
#define endl        "\n"
#define all1(a)     a+1,a+n+1
#define unordered_map  map
// #define push_back   emplace_back
// #define gcd(a,b)    __gcd(a,b);
// #define lcm(a,b)    (a*b)/gcd(a,b);

const long long INF = (long long)1e18;
const long long MOD = (long long)1e9+7;
const long long MODD = 2024; /// 998244353
const long long maxN = 1e6+9;
const int LOG = 31;
const int mlift = 19;


template<class A> inline int __lg(A &a) {  return static_cast<int>(log2(a));}
template<class A,class B> inline void add(A &a,B b) { a+=b;while (a>=MOD) a-=MOD;}
template<class A,class B> inline void minus(A &a,B b) { a-=b;while (a>=MOD) a-=MOD;while (a<0) a+=MOD;}






///--------------------------------


void solve();

signed main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);



    // file("BAI4");







    long long t;


    // cin >> t; 

    t=1;



    while (t--){




        solve();


    }





    cerr << "Time elapsed: " << TIME << "s.\n";
    cerr << "ducminh" << "\n";
    return 0;
}



///--------------------[PROBLEM SOLUTION]--------------------///



struct minh{
    long long v, mm1,mm2, pos;
};


vector<minh> a[200009];
long long luu[200009],n,cost[200009],f[200009],sl[200009],mm1[200009],mm2[200009];



// LCA

long long p[20][200005];

void DFS(long long u){
    for (long long i=0; i<a[u].size(); i++){

        long long v=a[u][i].v;
        if (p[0][u] != v){
            p[0][v]=u;
            cost[v]=cost[u]+a[u][i].mm1;
            luu[v]=luu[u]+1;
            for (long long i=1; i<=mlift; i++){
                p[i][v]= p[i-1][p[i-1][v]];
            }
            DFS(v);
        }
    }
}




long long LCA(long long u, long long v){


    if (luu[u]<luu[v]) swap(u,v);

    long long diff = luu[u]-luu[v];
    for (long long i=0; i<=mlift; i++){
        if ((diff>>i) & 1){
            u=p[i][u];
        } 
    }
    // cout << u << ' ' << v << "\n";

    if (u==v) return u;




    for (long long i=mlift; i>=0; i--){
        if (p[i][u]!=p[i][v]){
            u=p[i][u];
            v=p[i][v];
        }
    }




    return p[0][u];


}

long long lifting(long long u, long long k){
    for (long long i=0; i<=mlift; i++){
        if ((k>>i) & 1){
            u=p[i][u];
        }
    }

    return u;
}


long long getdist(long long u, long long v){

    return cost[u]+cost[v]-cost[LCA(u,v)];
}



long long dp[200009];
void dfs(long long u, long long par, long long pos){


    dp[u]=f[u];

    for (auto x: a[u]){
        if (x.v==par) continue;

        dfs(x.v,u,x.pos);
        dp[u]+=dp[x.v];
    }


    if (pos!=-1) sl[pos]=dp[u];
}

void solve(){


    cin >> n;

    for (long long i=1; i<n; i++){
        long long x, y;
        cin >> x >> y >> mm1[i] >> mm2[i];

        a[x].push_back({y,mm1[i],mm2[i],i});
        a[y].push_back({x,mm1[i],mm2[i],i});
    }


    DFS(1);


    // cout << LCA(1,2) << "\n";
    // cout << getdist(1,4) << "\n";
    

    for (long long i=1; i<n; i++){

        f[i]++;
        f[i+1]++;
        f[LCA(i,i+1)]-=2;
    }

    dfs(1,-1,-1);

    long long ans=0;
    for (long long i=1; i<n; i++){
        // cout << i << ' ' << sl[i] << ' ' << f[i] << "\n";
        

        ans+=min(mm1[i]*sl[i],mm2[i]);
    }

    cout << ans;


}

Compilation message (stderr)

putovanje.cpp: In function 'void DFS(long long int)':
putovanje.cpp:138:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<minh>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (long long i=0; i<a[u].size(); i++){
      |                         ~^~~~~~~~~~~~

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