Submission #1159731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159731		mnbvcxz123	Putovanje (COCI20_putovanje)	C++20	110 / 110	67 ms	23624 KiB

putovanje

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

#define ln '\n'
#define all(x) x.begin(), x.end()
#define forn(i, n) for(int i = 0; i < n; i++)
#define forab(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define sz(x) int(x.size())

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...)
#endif

typedef long long ll;

const int MAXN = 2e5 + 5;
const int LOG = log2(MAXN) + 1;
vector<int> g[MAXN];
int up[MAXN][LOG];
int deep[MAXN];
int pf[MAXN];

void dfs(int u, int p){
   deep[u] = deep[p] + 1;
   up[u][0] = p;

   forab(k, 1, LOG){
      up[u][k] = up[up[u][k - 1]][k - 1];
   }
   for(int v: g[u]){
      if(v == p) continue;
      dfs(v, u);
   }
}

int lca(int u, int v){
   if(deep[u] < deep[v]) swap(u, v);
   int df = abs(deep[u] - deep[v]);
   for(int k = LOG - 1; k >= 0; k--){
      if(df & (1LL << k)){
         u = up[u][k];
      }
   }
   if(u == v)return u;

   for(int k = LOG - 1; k >= 0; k--){
      if(up[u][k] != up[v][k]){
         u = up[u][k];
         v = up[v][k];
      }
   }
   return up[u][0];
}

void dfs2(int u, int p){
   for(int v: g[u]){
      if(v == p) continue;
      dfs2(v, u);
      pf[u] += pf[v];
   }
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   #ifdef LOCAL
      freopen("in.txt", "r", stdin);
      //freopen("out.txt", "w", stdout);
   #endif
   int n; cin >> n;
   vector<array<ll, 4>> edges(n - 1);
   forn(i, n - 1){
      int a, b, c1, c2;
      cin >> a >> b >> c1 >> c2;
      g[a].push_back(b);
      g[b].push_back(a);
      edges[i] = {a, b, c1, c2};
   }
   dfs(1, 0);
   forab(i, 1, n + 1) pf[i] = 0;
   forab(i, 1, n){
      pf[i]++;
      pf[i + 1]++;
      int lc = lca(i, i + 1);
      pf[lc]-=2;
   }
   dfs2(1, 0);
   ll ans = 0;
   for(auto [a, b, c1, c2] : edges){
      if(deep[a] < deep[b]) swap(a, b);
      ans += min(pf[a] * c1, c2);
   }
   cout << ans << ln;
   return 0;
}

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