Submission #234554

#	Time	Username	Problem	Language	Result	Execution time	Memory
234554		doowey	Putovanje (COCI20_putovanje)	C++14	110 / 110	142 ms	25336 KiB

putovanje

#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)] -= 2 ;
  }
  dfs2(1,-1);
  cout << ans << "\n";
  return 0;
}

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