Submission #1076331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076331		fryingduc	Putovanje (COCI20_putovanje)	C++17	110 / 110	92 ms	27872 KiB

putovanje

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

const int maxn = 2e5 + 5;
const int lg = 19;
int n, ca[maxn], cb[maxn];
vector<int> g[maxn];
int edge_u[maxn], edge_v[maxn], edge_ca[maxn], edge_cb[maxn];
int par[maxn];
int h[maxn];
int f[maxn];
int up[maxn][lg + 1];

void pre_dfs(int u, int prev) {
  for(auto v:g[u]) {
    if(v == prev) continue;
    par[v] = u;
    up[v][0] = u;
    h[v] = h[u] + 1;
    for(int i = 1; i <= lg; ++i) {
      up[v][i] = up[up[v][i - 1]][i - 1];
    }
    pre_dfs(v, u);
  }
}
int lca(int u, int v) {
  if(h[u] < h[v]) swap(u, v);
  for(int i = lg; i >= 0; --i) {
    if((h[u] - h[v]) >> i & 1) u = up[u][i];
  }
  if(u == v) return u;
  for(int i = lg; i >= 0; --i) {
    if(up[u][i] != up[v][i]) {
      u = up[u][i], v = up[v][i];
    }
  }
  return up[u][0];
}
void dfs(int u, int prev) {
  for(auto v:g[u]) {
    if(v == prev) continue;
    dfs(v, u);
    f[u] += f[v];
  }
}
void solve() {
  cin >> n;
  for(int i = 1; i < n; ++i) {
    int u, v, ca, cb; cin >> u >> v >> ca >> cb;
    g[u].push_back(v);
    g[v].push_back(u);
    edge_u[i] = u, edge_v[i] = v;
    edge_ca[i] = ca, edge_cb[i] = cb;
  }
  pre_dfs(1, 0);
  for(int i = 1; i < n; ++i) {
    int u = edge_u[i], v = edge_v[i];
    if(par[u] == v) swap(u, v);
    ca[v] = edge_ca[i], cb[v] = edge_cb[i];
  }
  for(int i = 1; i < n; ++i) {
    int u = i, v = i + 1;
    int l = lca(u, v);
    ++f[u], ++f[v];
    f[l] -= 2;
  }
  dfs(1, 0);
  long long ans = 0;
  for(int i = 2; i <= n; ++i) {
    ans += min(1ll * f[i] * ca[i], 1ll * cb[i]);
  }
  cout << ans;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  solve();
  return 0;
}

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