제출 #1045586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1045586		nmts	Putovanje (COCI20_putovanje)	C++17	110 / 110	92 ms	67156 KiB

putovanje

#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout);
#define faster    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define fi first
#define se second
#define mii map< int , int>
#define reset(a,val) memset(a ,val , sizeof(a) )
#define count_bit(i) __builtin_popcountll(i) 
#define mask(i) ((1LL << (i)))  
#define status(x, i) (((x) >> (i)) & 1)  
#define set_on(x, i) ((x) | mask(i)) 
#define set_off(x, i) ((x) & ~mask(i))
#define endl '\n'    
#define ll long long
#define int ll
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;


template <class T> inline T sqr(T x) { return x * x; };

template <class T> inline int Power(T x, int y) 

{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }

template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

inline int gcd(int x, int y) 
{ return y ? gcd(y , x % y) : x;}

inline int lcm(int x, int y) { return x * y / gcd(x, y); }

using namespace std;

int n , m;
vector<pair<int , pii>> edges[maxn];
int parent[maxn][LOG + 1];

int hight[maxn];
int cnt[maxn];
struct dl{
    int u , v , w1 , w2;
};
pii cost[maxn];
dl a[maxn];

void dfs(int u)
{

    for (auto v : edges[u])
        if ( v.fi != parent[u][0])
            {
                parent[v.fi][0] = u;
                hight[v.fi] = hight[u] + 1;
                cost[v.fi] = v.se;
                dfs(v.fi);
            }

}

void prepare()
{

    dfs(1);
    hight[0] = -1;

    for (int j = 1 ; j <= LOG ; ++j)
        for (int i = 1; i <= n ; ++i)
            parent[i][j] = parent[parent[i][j - 1]][j - 1];

}

int lca(int u , int v)
{

    if (u == 0) return v;
    if (v == 0) return u;
    if (hight[v] > hight[u]) return lca(v , u);

    for (int i = LOG ; i >= 0 ; --i)
        if (hight[parent[u][i]] >= hight[v]) u = parent[u][i];
    
    if (u == v) return u;

    for (int i = LOG ; i >= 0 ; --i)
        if (parent[u][i] != parent[v][i]) u = parent[u][i] , v = parent[v][i];
    
    return parent[v][0];


}

void dfs(int u , int p)
{

    for (auto v : edges[u])
        if (v.fi != p)
            {
                dfs(v.fi , u);
                cnt[u] += cnt[v.fi];
            }

}

void solve()
{

    cin >> n ;

    for (int i = 1 ; i < n ; ++i)
        {
            cin >> a[i].u >> a[i].v >> a[i].w1 >> a[i].w2;

            edges[a[i].u].push_back({a[i].v , {a[i].w1 , a[i].w2}});
            edges[a[i].v].push_back({a[i].u , {a[i].w1 , a[i].w2}});
        }        

    prepare();

    for (int i = 1 ; i < n ; ++i)
        {
            cnt[i]++;
            cnt[i + 1]++;
            cnt[lca(i , i+1)] -= 2;
        }
    
    dfs(1 , 0);

    ll ans = 0;

    for (int i = 2 ; i <= n ; ++i)
        ans += min(cost[i].fi * cnt[i] , cost[i].se);
    
    cout << ans << endl;

}


int32_t main()
{
    faster;
    // file("txt");
    // int t ; cin >> t ; while (t--)
    solve();
    return 0;
} 

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