제출 #234553

#제출 시각아이디문제언어결과실행 시간메모리
234553dooweyPutovanje (COCI20_putovanje)C++14
0 / 110
176 ms26488 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = (int)2e5 + 10; const int LOG = 20; vector<pii> T[N]; int idx[N]; ll cnt[N]; ll c1[N], c2[N]; int par[LOG][N]; int tin[N]; int tout[N]; int tt; void dfs(int u, int pr){ tin[u] = ++tt; par[0][u]=pr; for(int i = 1; i < LOG; i ++ ) par[i][u]=par[i-1][par[i-1][u]]; for(auto x : T[u]){ if(x.fi == pr) continue; idx[x.fi]=x.se; dfs(x.fi, u); } tout[u] = tt; } bool is_anc(int a, int b){ return tin[a] <= tin[b] && tout[a] >= tout[b]; } int lca(int a, int b){ if(is_anc(a,b))return a; if(is_anc(b,a))return b; for(int i = LOG - 1; i >= 0 ; i -- ) if(!is_anc(par[i][a],b))a=par[i][a]; return par[0][a]; } ll ans = 0; void dfs2(int u, int pr){ for(auto x : T[u]){ if(x.fi == pr) continue; dfs2(x.fi, u); cnt[u] += cnt[x.fi]; } if(pr == -1) return; ans += min(cnt[u] * 1ll * c1[idx[u]], c2[idx[u]]); } int main(){ fastIO; int n; cin >> n; int u, v; for(int i = 1; i < n; i ++ ){ cin >> u >> v >> c1[i] >> c2[i]; T[u].push_back(mp(v,i)); T[v].push_back(mp(u,i)); } dfs(1,1); for(int i = 1; i < n; i ++ ){ cnt[i]++; cnt[i+1]++; cnt[lca(i,i + 1)] -- ; } dfs2(1,-1); cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...