Submission #442851

#	Time	Username	Problem	Language	Result	Execution time	Memory
442851		mashrur_hossain	Putovanje (COCI20_putovanje)	C++17	110 / 110	243 ms	65044 KiB

putovanje

#include <bits/stdc++.h>
 
#define fast_cin         ios_base::sync_with_stdio(0); cin.tie(NULL); cerr.tie(NULL);
#define endl "\n"
#define dbg(x) cerr << #x << ": " << x << endl;
#define DBG    cerr << __LINE__ << ": I GOT STUCK\n";
 
using namespace std;    
typedef long long ll;
typedef long double db;
 
struct Edge{
    ll to;
    ll single, multi;
};
 
const ll mxn = 2e5 + 5;
ll n, LOG;
vector<Edge>adj[mxn];
vector<vector<ll>>up(mxn, vector<ll>(20));
ll in[mxn], out[mxn], sub[mxn];
ll timer, ans;
 
void dfs1(ll node, ll par, Edge to_parent){
    for(Edge child: adj[node]){
        if(child.to != par){
            dfs1(child.to, node, child);
            sub[node] += sub[child.to];
        }
    }
    if(par!= 0)ans+= min(sub[node]*to_parent.single, to_parent.multi);
}
 
void dfs2(ll node, ll par){
    in[node] = ++timer;
    up[node][0] = par;
    for(ll i = 1;i<=LOG;i++){
        up[node][i] = up[up[node][i-1]][i-1];
    }
    for(auto child: adj[node]){
        if(child.to != par){
            dfs2(child.to, node);
        }
    }
    out[node] = ++timer;
}
 
bool is_ancestor(ll u, ll v){
    // check if u is an ancestor of v
    return in[u] <= in[v] && out[u] >= out[v];
}
 
ll getlca(ll u, ll v){
    // get lca of u and v;
    if(is_ancestor(u,v))return u;
    if(is_ancestor(v,u))return v;
 
    for(ll i = LOG;i >=0; i--){
        if(!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
 
void solve(){
    cin >> n;
    LOG = (ll)log2(n) + 1;
    for(ll i =0;i<n-1;i++){
        ll u, v, c1, c2;
        cin >> u >> v >> c1 >> c2;
        Edge e = {v, c1, c2};
        adj[u].emplace_back(e);
        e.to = u;
        adj[v].emplace_back(e);
    }
 
    dfs2(1,1);
    for(ll i =1;i<n;i++){
        ll lca = getlca(i, i+1);
        if(lca == i){
            sub[i]--;
            sub[i+1]++;
        }
        else if(lca == i+1){
            sub[i]++;
            sub[i+1]--;
        }
        else{
            sub[i] ++;
            sub[i+1]++;
            sub[lca]-=2;
        }
    }
    Edge e = {0, 0, 0};
    dfs1(1, 0, e);
    cout << ans << endl;
}
 
int main() {
    fast_cin;
    int test;test = 1;
    // int test;cin >>test;
    while(test--){
        solve();
    }
    return 0;
}

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