Submission #344937

#	Time	Username	Problem	Language	Result	Execution time	Memory
344937		limabeans	Putovanje (COCI20_putovanje)	C++17	110 / 110	195 ms	26220 KiB

putovanje

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;




const int maxn = 2e5 + 10;
const int LOG = 18;

int n;
pair<ll,ll> edge[maxn];
vector<pair<int,int>> g[maxn];


int dep[maxn];
int par[LOG+1][maxn];

void dfs(int at, int p) {
    for (int i=1; i<LOG; i++) {
	par[i][at] = par[i-1][par[i-1][at]];
    }
    
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	dep[to]=1+dep[at];
	par[0][to]=at;
	dfs(to,at);
    }
}

ll dp[maxn];

int lca(int u, int v) {
    if (dep[u]<dep[v]) swap(u,v);
    int dx = dep[u]-dep[v];
    for (int i=LOG-1; i>=0; i--) {
	if (dx>>i&1) {
	    u = par[i][u];
	}
    }

    if (u==v) return u;

    for (int i=LOG-1; i>=0; i--) {
	if (par[i][u] != par[i][v]) {
	    u = par[i][u];
	    v = par[i][v];
	}
    }

    return par[0][u];
}


ll edUsage[maxn];

void dfs2(int at, int p) {
    int edId = -1;
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to==p) {
	    edId = ed.first;
	} else {
	    dfs2(to, at);
	}
    }

    if (~edId) {
	edUsage[edId] += dp[at];
	dp[p] += dp[at];
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	int c0,c1;
	cin>>c0>>c1;
	g[u].push_back({i,v});
	g[v].push_back({i,u});
	edge[i] = {c0,c1};
    }

    dfs(1, 0);

    for (int i=1; i<n; i++) {
	int j=i+1;
	int mid = lca(i,j);
	//cout<<i<<"-->"<<j<<": "<<mid<<endl;
	dp[i]++;
	dp[j]++;
	dp[mid]--;
	dp[mid]--;
    }

    dfs2(1, 0);


    ll res = 0;

    for (int i=0; i<n-1; i++) {
	res += min(edge[i].second, edUsage[i]*edge[i].first);
    }


    cout<<res<<endl;



    // for (int i=0; i<n-1; i++) {
    // 	cout<<edUsage[i]<<" ";
    // }
    // cout<<endl;
    
    return 0;
}

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