Submission #1093571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093571		vjudge1	Putovanje (COCI20_putovanje)	C++17	110 / 110	119 ms	33224 KiB

putovanje

#include <iostream>
#include <vector>
#include <array>
#include <map>

using namespace std;

using ll = long long;
using pii = array<int, 2>;
const int maxn = 200'001;
const int LOG = 19;

int n;
vector<int> tree[maxn];

int used[maxn], 
seen[maxn],
depth[maxn],
ancestor[LOG][maxn];

pii cost[maxn];
map<pii, int> ident; 

void dfs(int u, int p, int d){
  ancestor[0][u] = p;
  depth[u] = d;
  for(int & v : tree[u])
    if(v != p)
      dfs(v, u, d + 1);
}

void calculateFrequencyOfEdge(int u, int p){
  for(int & v : tree[u])
    if(v != p){
      calculateFrequencyOfEdge(v, u);
      seen[u] += seen[v];
    }
  if(u != p)
    used[ident[{min(u, p), max(u, p)}]] += seen[u];
}

int main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for(int i = 0; i < (n - 1); i++){
    int a, b, c1, c2;
    cin >> a >> b >> c1 >> c2;
    tree[a].emplace_back(b);
    tree[b].emplace_back(a);
    cost[i] = {c1, c2};
    ident[{min(a, b), max(a, b)}] = i;
  }
  dfs(1, 1, 0);
  for(int i = 1; i < LOG; i++)
    for(int u = 1; u <= n; u++)
      ancestor[i][u] = ancestor[i - 1][ancestor[i - 1][u]];
  for(int a = 1; a <= (n - 1); a++){
    int b = (a + 1);
    int _a = a, _b = b;
    if(depth[_b] > depth[_a])
      swap(_a, _b);
    int dif = depth[_a] - depth[_b];
    for(int i = LOG - 1; i >= 0; i--)
      if((1 << i) & dif)
        _a = ancestor[i][_a];
    if(_b == _a){
      if(depth[b] > depth[a]){
        ++seen[b];
        --seen[a];
      } else {
        ++seen[a];
        --seen[b];
      }
    } else {
      for(int i = LOG - 1; i >= 0; i--)
        if(ancestor[i][_a] != ancestor[i][_b])
          _a = ancestor[i][_a],
          _b = ancestor[i][_b];
      _a = ancestor[0][_a];
      ++seen[a];
      ++seen[b];
      seen[_a] -= 2;
    }
  }
  calculateFrequencyOfEdge(1, 1);
  ll answer = 0;
  for(int i = 0; i < (n - 1); i++){
    answer += min((ll) cost[i][1], (ll) used[i]*cost[i][0]);
  }
  cout << answer << '\n';
}

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