oj.uz

Submission #1051132

# Submission time Handle Problem Language Result Execution time Memory
1051132 2024-08-09T20:36:10 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278612 KB 
#include<bits/stdc++.h>
#define pii pair<int , int>
#define pli pair<long long , int>
#include "factories.h"
using namespace std;
const int MAX = 5e5 + 1 , B = 700 , LOG = 20;
const long long oo = 1e16;
int T = 0 , n , d[MAX] , in[MAX];
long long D[MAX];
vector<int> g[MAX] , order = {0};
vector<long long> w[MAX];
pii mn[2 * MAX][LOG];
void dfs(int u , int p = 0){
   order.push_back(u);
   in[u] = ++T;
   d[u] = d[p] + 1;
   for(int x = 0;x < (int)g[u].size();x ++){
      if(g[u][x] != p){
         D[g[u][x]] = D[u] + w[u][x];
         dfs(g[u][x] , u);
         T++;
         order.push_back(u);
      }
   }
}
pii MERGE(pii x , pii y){
   if(x.second > y.second){
      swap(x , y);
   }
   return x;
}
int lca(int u , int v){
  // cout << u << " " << v << " " << in[u] << " " << in[v] << endl;
   if(in[u] > in[v]){
      swap(u , v);
   }
   int sz = 31 - __builtin_clz(in[v] - in[u] + 1);
   //cout << mn[in[v] - (1 << sz) + 1][sz].first << " " << mn[in[v] - (1 << sz) + 1][sz].second << endl;
   return MERGE(mn[in[u]][sz] , mn[in[v] - (1 << sz) + 1][sz]).first;
}
void Init(int N , int A[] , int B[] , int D[]){
   n = N;
   for(int i = 0;i < N - 1;i ++){
      ++A[i] , ++B[i];
      g[A[i]].push_back(B[i]);
      w[A[i]].push_back(D[i]);
      g[B[i]].push_back(A[i]);
      w[B[i]].push_back(D[i]);
   }
   dfs(1);
   for(int bit = 0;bit < LOG;bit ++){
      if(bit == 0){
         for(int i = 1;i < (int)order.size();i ++){
            mn[i][bit] = {order[i] , d[order[i]]};
         }
      }else{
         for(int i = 1;i + (1 << bit) - 1 < (int)order.size();i ++){
            mn[i][bit] = MERGE(mn[i][bit - 1] , mn[i + (1 << (bit - 1))][bit - 1]);
         }
      }
   }
}
long long Query(int S , int X[] , int T , int Y[]){
   long long ans = oo;
   for(int i = 0;i < S;i ++){
      ++X[i];
   }
   for(int i = 0;i < T;i ++){
      ++Y[i];
   }
   if(T > B){
      vector<long long> e(n + 1 , -1);
      priority_queue<pli , vector<pli> , greater<pli>> pq;
      for(int i = 0;i < T;i ++){
         e[Y[i]] = 0LL;
         pq.push({0LL , Y[i]});
      }
      while(pq.size()){
         auto [s , u] = pq.top();
         pq.pop();
         if(s != e[u]){
            continue;
         }
         for(int x = 0;x < (int)g[u].size();x ++){
            if(e[g[u][x]] == -1 || e[g[u][x]] > s + w[u][x]){
               e[g[u][x]] = s + w[u][x];
               pq.push({e[g[u][x]] , g[u][x]});
            }
         }
      }
      for(int i = 0;i < S;i ++){
         ans = min(ans , e[X[i]]);
      }
   }else{
      for(int i = 0;i < S;i ++){
         for(int j = 0;j < T;j ++){
            ans = min(ans , D[X[i]] + D[Y[j]] - 2 * D[lca(X[i] , Y[j])]);
         }
      }
   }
   return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24408 KB Output is correct
2 Correct 1368 ms 34244 KB Output is correct
3 Correct 1345 ms 34040 KB Output is correct
4 Correct 1544 ms 34040 KB Output is correct
5 Correct 1386 ms 34384 KB Output is correct
6 Correct 1280 ms 52584 KB Output is correct
7 Correct 1201 ms 52308 KB Output is correct
8 Correct 360 ms 52580 KB Output is correct
9 Correct 1283 ms 52560 KB Output is correct
10 Correct 1221 ms 52592 KB Output is correct
11 Correct 1190 ms 52304 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 45552 KB Output is correct
2 Correct 649 ms 248400 KB Output is correct
3 Correct 696 ms 251408 KB Output is correct
4 Correct 524 ms 250784 KB Output is correct
5 Correct 675 ms 278612 KB Output is correct
6 Correct 683 ms 251380 KB Output is correct
7 Correct 413 ms 94052 KB Output is correct
8 Correct 298 ms 92088 KB Output is correct
9 Correct 279 ms 97392 KB Output is correct
10 Correct 289 ms 92360 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24408 KB Output is correct
2 Correct 1368 ms 34244 KB Output is correct
3 Correct 1345 ms 34040 KB Output is correct
4 Correct 1544 ms 34040 KB Output is correct
5 Correct 1386 ms 34384 KB Output is correct
6 Correct 1280 ms 52584 KB Output is correct
7 Correct 1201 ms 52308 KB Output is correct
8 Correct 360 ms 52580 KB Output is correct
9 Correct 1283 ms 52560 KB Output is correct
10 Correct 1221 ms 52592 KB Output is correct
11 Correct 1190 ms 52304 KB Output is correct
12 Correct 6 ms 45552 KB Output is correct
13 Correct 649 ms 248400 KB Output is correct
14 Correct 696 ms 251408 KB Output is correct
15 Correct 524 ms 250784 KB Output is correct
16 Correct 675 ms 278612 KB Output is correct
17 Correct 683 ms 251380 KB Output is correct
18 Correct 413 ms 94052 KB Output is correct
19 Correct 298 ms 92088 KB Output is correct
20 Correct 279 ms 97392 KB Output is correct
21 Correct 289 ms 92360 KB Output is correct
22 Correct 6819 ms 255424 KB Output is correct
23 Execution timed out 8060 ms 253676 KB Time limit exceeded
24 Halted 0 ms 0 KB -