제출 #852288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852288		hungnt	Putovanje (COCI20_putovanje)	C++14	110 / 110	77 ms	34736 KiB

putovanje

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 200005;

int n;
long long c[N], d[N];
int h[N], par[N][25], dp[N], cnt[N], s[N];
vector<pair<int, int>> adj[N];

void dfs(int u, int p, int t)
{
    h[u] = t;
    par[u][0] = p;
    for(auto v : adj[u])
        if(v.fi != p)
            dfs(v.fi, u, t + 1);
}

int lca(int u, int v)
{
    if(h[u] < h[v]) swap(u, v);
    int diff = h[u] - h[v];
    for(int i = 20; i >= 0; i--)
        if(diff & (1 << i))
            u = par[u][i];
    if(u == v) return u;
    for(int i = 20; i >= 0; i--)
        if(par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];

        }
    return par[v][0];
}

void calc(int u, int p, int id)
{
    for(auto x : adj[u])
        if(x.fi != p)
        {
            calc(x.fi, u, x.se);
            dp[u] += dp[x.first];
        }
    dp[u] += s[u];
    cnt[id] = dp[u];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n;
    int u, v;
    for(int i = 1; i < n; i++)
    {
        cin >> u >> v >> c[i] >> d[i];
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    dfs(1, 0, 0);
    for(int i = 1; (1 << i) <= n; i++)
        for(int j = 1; j <= n; j++)
            par[j][i] = par[par[j][i - 1]][i - 1];
    for(int i = 1; i < n; i++)
    {
        s[i]++;
        s[i + 1]++;
        s[lca(i, i + 1)] -= 2;
    }
    calc(1, 0, 0);
    long long ans = 0;
    for(int i = 1; i <= n; i++)
        ans += min(cnt[i] * c[i], d[i]);
    cout << ans;
}

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