Submission #212136

#	Time	Username	Problem	Language	Result	Execution time	Memory
212136		Kalam	Putovanje (COCI20_putovanje)	C++11	110 / 110	164 ms	30088 KiB

putovanje

// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 200000 + 77;

struct Tree {
   int n , tim = 1 , d[N] , up[N] , par[N] , sz[N] , st[N] , en[N] , who[N];
   vector < int > adj[N];
   void dfsSz(int v) {
      sz[v] = 1;
      for(int u : adj[v]) {
         if(find(adj[u].begin() , adj[u].end() , v) != adj[u].end())
            adj[u].erase(find(adj[u].begin() , adj[u].end() , v));
         d[u] = d[v] + 1;
         par[u] = v;
         dfsSz(u);
         sz[v] += sz[u];
      }
   }
   void dfsHv(int v) {
      who[tim] = v;
      st[v] = tim ++;
      sort(adj[v].begin() , adj[v].end() , [&](int x , int y) { return sz[x] > sz[y];});
      int cnt = 0;
      for(int u : adj[v]) {
         up[u] = u;
         if(cnt ++ == 0)
            up[u] = up[v];
         dfsHv(u);
      }
      en[v] = tim;
   }
   inline int GetLca(int v , int u) {
      while(up[v] != up[u]) {
         if(d[up[v]] < d[up[u]])
            swap(v , u);
         v = par[up[v]];
      }
      if(d[v] > d[u])
         swap(v , u);
      return v;
   }
   inline int GetPar(int v , int k) {
      while(d[v] - d[up[v]] < k)
         k -= d[v] - d[up[v]] + 1 , v = par[up[v]];
      return who[st[v] - k];
   }
   inline int GetKth(int v , int u , int k) {
      int Lca = GetLca(v , u);
      if(k <= d[v] - d[Lca] + 1)
         return GetPar(v , k - 1);
      k -= d[v] - d[Lca] + 1;
      return GetPar(u , d[u] - d[Lca] - k);
   }
   inline int GetDistance(int v , int u) {
      return d[v] + d[u] - (d[GetLca(v , u)] << 1);
   }
   void BuildHLD(int root) {
      for(int i = 0;i < N;++ i)
         d[i] = st[i] = en[i] = sz[i] = par[i] = up[i] = who[i] = 0;
      tim = 1;
      up[root] = root;
      dfsSz(root);
      dfsHv(root);
   }
} Tree;
long long A;
int n , Ev[N] , Eu[N] , C1[N] , C2[N] , dp[N];
vector < int > adj[N];
void dfs(int v , int prev = -1) {
   for(int u : adj[v])
      if(u != prev)
         dfs(u , v) , dp[v] += dp[u];
}
int main() {
   scanf("%d" , & n);
   for(int i = 1;i < n;++ i) {
      scanf("%d %d %d %d" , Ev + i , Eu + i , C1 + i , C2 + i);
      Tree.adj[Ev[i]].push_back(Eu[i]);
      Tree.adj[Eu[i]].push_back(Ev[i]);
      adj[Ev[i]].push_back(Eu[i]);
      adj[Eu[i]].push_back(Ev[i]);
   }
   Tree.BuildHLD(1);
   for(int i = 1;i < n;++ i) {
      int lca = Tree.GetLca(i , i + 1);
      ++ dp[i];++ dp[i + 1];
      dp[lca] -= 2;
   }
   dfs(1);
   for(int i = 1;i < n;++ i) {
      if(Tree.d[Ev[i]] > Tree.d[Eu[i]])
         swap(Ev[i] , Eu[i]);
      if(dp[Eu[i]] * 1ll * C1[i] >= C2[i])
         A += C2[i];
      else
         A += C1[i] * 1ll * dp[Eu[i]];
   }
   printf("%lld\n" , A);
   return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d" , & n);
    ~~~~~^~~~~~~~~~~~
putovanje.cpp:80:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d %d" , Ev + i , Eu + i , C1 + i , C2 + i);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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