Submission #460427

#	Time	Username	Problem	Language	Result	Execution time	Memory
460427		ak2006	Putovanje (COCI20_putovanje)	C++14	110 / 110	299 ms	59800 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
ll n = 2e5 + 5,TIMER;
vvvl adj(n);
vvi anc(n,vi(21));
vl pref(n);
vl in(n),out(n),weight1ToParent(n),weight2ToParent(n);
void dfs(int u,int p)
{
    in[u] = ++TIMER;
    anc[u][0] = p;
    for (int i = 1;i<=20;i++)anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (auto val:adj[u]){
        int v = val[0];
        if (v != p){
            weight1ToParent[v] = val[1];
            weight2ToParent[v] = val[2];
            dfs(v,u);
        }
    }
    out[u] = ++TIMER;
}
void dfs2(int u,int p)
{
    for (auto val:adj[u]){
        int v = val[0];
        if (v != p){
            dfs2(v,u);
            pref[u] += pref[v];
        }
    }
}
bool is_ancestor(int u,int v)
{
    return in[u] <= in[v] && out[u] >= out[v];
}
int LCA(int u,int v)
{
    if (in[u] > in[v])swap(u,v);
    if (is_ancestor(u,v))return u;
    for (int i = 20;i>=0;i--)
        if (!is_ancestor(anc[v][i],u))v = anc[v][i];
    return anc[v][0];
}
int main()
{
    setIO();
    cin>>n;
    for (int i = 1;i<=n - 1;i++){
        int u,v,w1,w2;
        cin>>u>>v>>w1>>w2;
        adj[u].pb({v,w1,w2});
        adj[v].pb({u,w1,w2});
    }
    dfs(1,1);
    for (int i = 1;i<=n - 1;i++){
        int u = i,v = i + 1;
        int l = LCA(u,v);
        // while (u != l){
        //     pref[u]++;
        //     u = anc[u][0];
        // }
        // while (v != l){
        //     pref[v]++;
        //     v = anc[v][0];
        // }

        if (u != l and v != l){
            pref[u]++;
            pref[v]++;
            pref[l]--;
            pref[l]--;
        }
        else{
            if (u == l){
                pref[u]--;
                pref[v]++;
            }
            else{
                pref[v]--;
                pref[u]++;
            }
        }
    }
    dfs2(1,1);
    ll ans = 0;
    for (int i = 2;i<=n;i++)
        ans += min(pref[i] * weight1ToParent[i],weight2ToParent[i]);
    cout<<ans;
    return 0;
}

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