Submission #793562

#	Time	Username	Problem	Language	Result	Execution time	Memory
793562		vjudge1	Putovanje (COCI20_putovanje)	C++17	110 / 110	253 ms	40372 KiB

putovanje

#include<bits/stdc++.h>
using namespace std;

const int N = 200100;
const int K = 20;

vector<int> adj[N];
int pai[N][K], in[N], out[N], cs = 0;
long long cost[N];

void pre_dfs(int u, int p)
{
    in[u] = cs++;
    pai[u][0] = p;
    for(int i = 1; i < K; i++)
        pai[u][i] = pai[pai[u][i-1]][i-1];
    for(int v : adj[u])
        if(v != p)
            pre_dfs(v, u);
    out[u] = cs++;
}

// u is ancestor of v ?
bool is_ancestor(int u, int v)
{
    return in[u] <= in[v] && out[v] <= out[u];
}

int calc_lca(int a, int b)
{
    if(is_ancestor(a, b))
        return a;
    if(is_ancestor(b, a))
        return b;
    for(int i = K-1; i >=0; i--)
    {
        if(!is_ancestor(pai[b][i], a))
            b = pai[b][i];
    }
    return pai[b][0];
}

map<pair<int,int>,pair<int,int>> mp;

long long rs = 0;

void dfs(int u, int p)
{
    for(int v : adj[u])
        if(v != p)
        {
            dfs(v, u);
            cost[u] += cost[v];
        }

    rs += min(mp[{u,p}].first*cost[u],(long long)mp[{u,p}].second);
}


void test()
{
    int n;
    cin >> n;
    for(int i = 0, u, v, c1, c2; i < n-1; i++)
    {
        cin >> u >> v >> c1 >> c2;
        mp[{u,v}] = mp[{v,u}] = {c1,c2};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    pre_dfs(1, 1);
    for(int i = 1; i < n; i++)
    {
        int lc = calc_lca(i, i+1);
        cost[lc] -=2;
        cost[i] += 1;
        cost[i+1] += 1;
    }
    dfs(1, 1);
    cout << rs << '\n';
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    test();

    return 0;
}

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