제출 #1138032

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138032		Psiuk_Yurii	Putovanje (COCI20_putovanje)	C++20	0 / 110	74 ms	42632 KiB

putovanje

/*In FISH at EGOI25 I trust*/
/*In FISH at EGOI25 I trust*/
/*In FISH at EGOI25 I trust*/
/*In FISH at EGOI25 I trust*/
/*In FISH at EGOI25 I trust*/
#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppl;

struct edge{
   ll to,a,b;
};
ll n,v1,v2,a,b,dv[200009][29],h,timer,tin[200009],tout[200009],d[200009],c[200009],res;
vector<edge> A[200009];
void dfs(int v,int par){
   timer++;
   tin[v]=timer;
   dv[v][0]=par;
   d[v]=d[par]+1;
   for(int i=1;i<=h;i++) dv[v][i]=dv[dv[v][i-1]][i-1];
   for(auto x:A[v]) {
      if(x.to==par) continue;
      dfs(x.to,v);
   }
   timer++;
   tout[v]=timer;
}
bool is(ll a,ll b){
   if(tin[a]<=tin[b] && tout[b]<=tout[a]) return true;
   else return false;
}
ll lca(ll a,ll b){
    if(d[a]>d[b]) swap(a,b);
   if(is(a,b)) return a;
   for(int i=h;i>=0;i--) {
      if(!is(dv[b][i],a)) b=dv[b][i];
   }
   return dv[b][0];
}
ll dfs2(ll v){
    ll u=c[v];
    ll C=0; ll B=0;

   for(auto x:A[v]){
      if(d[x.to]<d[v]) {
        C=x.a;
        B=x.b;
        continue;
      }
      u+=dfs2(x.to);
   }
   res+=min(u*C,B);
   return u;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    h=22;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>v1>>v2>>a>>b;
        A[v1].push_back({v2,a,b});
        A[v2].push_back({v1,a,b});
    }
    dfs(1,1);
    for(int i=1;i<n;i++) {
       ll lc=lca(i,i+1);
       c[i]++;
       c[i+1]++;
       c[lc]--;
       c[dv[lc][0]]--;
    }
    dfs2(1);
    cout<<res<<endl;

    return 0;
}

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