Submission #477026

#	Time	Username	Problem	Language	Result	Execution time	Memory
477026		mychecksedad	Putovanje (COCI20_putovanje)	C++17	25 / 110	119 ms	37816 KiB

putovanje

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 2e5 + 10, M = 1e5+10, F = 2147483646, K = 20;



int n, a, b, depth[N], timein[N], lca[4*N][K];
vector<pair<int, pair<ll, ll>>> g[N];
vector<int> euler;
pair<int, int> s[N];
ll ans = 0, m[N], sum = 0;
void dfs(int v, int p, int d){
    depth[v] = d;
    timein[v] = int(euler.size());
    euler.pb(v);
    for(auto k: g[v]){
        if(k.first != p){
            dfs(k.first, v, d + 1);
            euler.pb(v);
        }
    }
}
int mx(int l, int r){
    int k = __lg(r - l + 1);
    if(depth[lca[l][k]] < depth[lca[r - (1<<k) + 1][k]])
        return lca[l][k];
    return lca[r - (1<<k) + 1][k];
}
void ans_dfs(int v, int p){
    for(auto k: g[v]){
        if(k.first != p){
            ans_dfs(k.first, v);
            ans += min(sum * k.second.first, k.second.second);
             // cout << sum << ' ' << v << ' ' << k.first << ' ' << m[v] << '\n';
            sum -= m[v];
            m[v] = 0;
        }
    }
    ++m[s[v].first];
    ++m[s[v].second];
    if(s[v].first != 0) ++sum;
    if(s[v].second != 0) ++sum;
}
int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i < n - 1; ++i){
        ll w1, w2;
        cin >> a >> b >> w1 >> w2;
        g[a].pb({b, {w1, w2}});
        g[b].pb({a, {w1, w2}});
    }
    for(int i = 1; i <= n; i++) timein[i] = 1e9, s[i] = {0, 0};
    dfs(1, 0, 0);
    for(int i = 0; i < int(euler.size()); i++) lca[i][0] = euler[i];
    for(int j = 1; j < K; ++j){
        for(int i = 0; i + (1 << (j-1)) <= int(euler.size()); ++i){
            if(depth[lca[i][j - 1]] < depth[lca[i + (1<<(j-1))][j - 1]]) lca[i][j] = lca[i][j - 1];
            else lca[i][j] = lca[i + (1<<(j-1))][j - 1];
        }
    }
    for(int i = 1; i < n; i++){
        int node = mx(min(timein[i], timein[i + 1]), max(timein[i + 1], timein[i]));
        if(node != i)
            s[i].second = node;
        if(node != i + 1)
            s[i + 1].first = node;
    }
    // for(int i = 1; i <= n; i++) cout << s[i].first << ' ' << s[i].second << '\n';
    sum = 0;
    ans_dfs(1, 0);
    cout << ans;

    return 0;
}

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