Submission #1132426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132426		DangKhoizzzz	Putovanje (COCI20_putovanje)	C++20	110 / 110	128 ms	34536 KiB

putovanje

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>
using namespace std;

const int INF = 1e9 + 7;
const int maxn = 2e5 + 7;

vector <arr3> g[maxn];
int n , cost1[maxn] , cost2[maxn] , jump[maxn][20] , dep[maxn] , cnt[maxn];

void dfs(int u , int p)
{
    for(arr3 tmp: g[u])
    {
        int v = tmp[0];
        if(v == p) continue;
        dep[v] = dep[u] + 1;
        jump[v][0] = u;
        cost1[v] = tmp[1];
        cost2[v] = tmp[2];
        dfs(v , u);
    }
}

void build()
{
    dfs(1 , 1);
    for(int j = 1; j < 20; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    }
}

int LCA(int u , int v)
{
    if(dep[u] < dep[v]) swap(u , v);

    for(int i = 19; i >= 0; i--)
    {
        if(dep[jump[u][i]] >= dep[v])
        {
            u = jump[u][i];
        }
    }
    if(u == v) return u;

    for(int i = 19; i >= 0; i--)
    {
        if(jump[u][i] != jump[v][i])
        {
            u = jump[u][i];
            v = jump[v][i];
        }
    }
    return jump[u][0];
}

void add_dfs(int u , int p)
{
    for(arr3 tmp: g[u])
    {
        int v = tmp[0];
        if(v == p) continue;

        add_dfs(v , u);
        cnt[u] += cnt[v];
    }
}

void solve()
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u , v , w1 , w2;
        cin >> u >> v >> w1 >> w2;
        g[u].push_back({v , w1 , w2});
        g[v].push_back({u , w1 , w2});
    }
    build();

    for(int i = 1; i < n; ++i)
    {
        cnt[i]++; cnt[i+1]++;
        cnt[LCA(i , i+1)] -=2;
    }
    add_dfs(1 , 1);

    int ans = 0;

    for(int i = 1; i <= n; i++)
    {
        ans += min(cnt[i]*cost1[i] , cost2[i]);
    }
    cout << ans << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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