Submission #246435

#	Time	Username	Problem	Language	Result	Execution time	Memory
246435		alrad	Putovanje (COCI20_putovanje)	C++17	110 / 110	139 ms	26712 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()

const int N = 2e5 + 2;
const int LOG = 19;

int L = 1 , timer = 0;
int tin[N] , tout[N] , c[N] , d[N];
int up[N][LOG] , cnt[N] , p[N] , dp[N];
vector<vector<pair<int , int> > > g(N , vector<pair<int , int> >());

void dfs1(int v , int p = 1) {
   tin[v] = ++timer;
   up[v][0] = p;
   for (int i = 1; i <= L; i++) {
      up[v][i] = up[up[v][i - 1]][i - 1];
   }
   for (auto e : g[v]) {
      int to = e.first;
      int pos = e.second;
      if (to != p) {
         dfs1(to , v);
      }
   }
   tout[v] = ++timer;
}

bool ancestor(int a , int b) {
   return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a , int b) {
   if (ancestor(a , b)) {
      return a;
   }
   if (ancestor(b , a)) {
      return b;
   }
   for (int i = L; i >= 0; --i) {
      if (!ancestor(up[a][i] , b)) {
         a = up[a][i];
      }
   }
   return up[a][0];
}

void dfs(int v , int par = -1 , int in = -1) {
   for (auto e : g[v]) {
      int to = e.first;
      int edgeNum = e.second;
      if (to != par) {
         dfs(to , v , edgeNum);
         dp[v] += dp[to];
      }
   }
   dp[v] += p[v];
   if (in != -1) {
      cnt[in] = dp[v];
   }
}

int main() {
   #ifdef judge
      ifstream cin("input.txt");
   #endif // judge
   ios_base :: sync_with_stdio(0);
   cin.tie(0) , cout.tie(0);
   int n;
   cin >> n;
   while ((1 << L) <= n) {
      L++;
   }
   for (int i = 0; i < n - 1; i++) {
      int u , v;
      cin >> u >> v >> c[i] >> d[i];
      g[u].push_back({v , i});
      g[v].push_back({u , i});
   }
   dfs1(1);
   for (int i = 1; i < n; i++) {
      int anc = lca(i , i + 1);
      p[i]++ , p[i + 1]++;
      p[anc] -= 2;
   }
   dfs(1 , -1);
   long long ans = 0LL;
   for (int i = 0; i < n - 1; i++) {
      ans += min(c[i] * 1LL * cnt[i] , 1LL * d[i]);
   }
   cout << ans << '\n';
   return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'void dfs1(int, int)':
putovanje.cpp:23:11: warning: unused variable 'pos' [-Wunused-variable]
       int pos = e.second;
           ^~~

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