oj.uz

Submission #1051138

# Submission time Handle Problem Language Result Execution time Memory
1051138 2024-08-09T20:40:58 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278732 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 = 50 , 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 45660 KB Output is correct
2 Correct 651 ms 52220 KB Output is correct
3 Correct 1978 ms 52228 KB Output is correct
4 Correct 1489 ms 52308 KB Output is correct
5 Correct 636 ms 52564 KB Output is correct
6 Correct 634 ms 52824 KB Output is correct
7 Correct 1963 ms 52412 KB Output is correct
8 Correct 339 ms 52540 KB Output is correct
9 Correct 622 ms 52564 KB Output is correct
10 Correct 648 ms 52608 KB Output is correct
11 Correct 1978 ms 52416 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 45660 KB Output is correct
2 Correct 677 ms 248496 KB Output is correct
3 Correct 695 ms 251220 KB Output is correct
4 Correct 530 ms 250532 KB Output is correct
5 Correct 683 ms 278732 KB Output is correct
6 Correct 680 ms 251480 KB Output is correct
7 Correct 355 ms 90308 KB Output is correct
8 Correct 304 ms 92216 KB Output is correct
9 Correct 277 ms 95328 KB Output is correct
10 Correct 320 ms 92612 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 45660 KB Output is correct
2 Correct 651 ms 52220 KB Output is correct
3 Correct 1978 ms 52228 KB Output is correct
4 Correct 1489 ms 52308 KB Output is correct
5 Correct 636 ms 52564 KB Output is correct
6 Correct 634 ms 52824 KB Output is correct
7 Correct 1963 ms 52412 KB Output is correct
8 Correct 339 ms 52540 KB Output is correct
9 Correct 622 ms 52564 KB Output is correct
10 Correct 648 ms 52608 KB Output is correct
11 Correct 1978 ms 52416 KB Output is correct
12 Correct 6 ms 45660 KB Output is correct
13 Correct 677 ms 248496 KB Output is correct
14 Correct 695 ms 251220 KB Output is correct
15 Correct 530 ms 250532 KB Output is correct
16 Correct 683 ms 278732 KB Output is correct
17 Correct 680 ms 251480 KB Output is correct
18 Correct 355 ms 90308 KB Output is correct
19 Correct 304 ms 92216 KB Output is correct
20 Correct 277 ms 95328 KB Output is correct
21 Correct 320 ms 92612 KB Output is correct
22 Correct 7344 ms 255300 KB Output is correct
23 Execution timed out 8103 ms 253428 KB Time limit exceeded
24 Halted 0 ms 0 KB -