oj.uz

Submission #1051133

# Submission time Handle Problem Language Result Execution time Memory
1051133 2024-08-09T20:37:11 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278616 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 = 300 , 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 14 ms 45656 KB Output is correct
2 Correct 729 ms 52308 KB Output is correct
3 Correct 1202 ms 52308 KB Output is correct
4 Correct 1218 ms 52396 KB Output is correct
5 Correct 702 ms 52824 KB Output is correct
6 Correct 671 ms 52600 KB Output is correct
7 Correct 1208 ms 52392 KB Output is correct
8 Correct 349 ms 52576 KB Output is correct
9 Correct 708 ms 52816 KB Output is correct
10 Correct 699 ms 52652 KB Output is correct
11 Correct 1198 ms 52564 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45656 KB Output is correct
2 Correct 640 ms 248520 KB Output is correct
3 Correct 703 ms 251316 KB Output is correct
4 Correct 530 ms 250532 KB Output is correct
5 Correct 686 ms 278616 KB Output is correct
6 Correct 672 ms 251320 KB Output is correct
7 Correct 379 ms 90216 KB Output is correct
8 Correct 273 ms 90476 KB Output is correct
9 Correct 283 ms 93808 KB Output is correct
10 Correct 296 ms 90736 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 45656 KB Output is correct
2 Correct 729 ms 52308 KB Output is correct
3 Correct 1202 ms 52308 KB Output is correct
4 Correct 1218 ms 52396 KB Output is correct
5 Correct 702 ms 52824 KB Output is correct
6 Correct 671 ms 52600 KB Output is correct
7 Correct 1208 ms 52392 KB Output is correct
8 Correct 349 ms 52576 KB Output is correct
9 Correct 708 ms 52816 KB Output is correct
10 Correct 699 ms 52652 KB Output is correct
11 Correct 1198 ms 52564 KB Output is correct
12 Correct 5 ms 45656 KB Output is correct
13 Correct 640 ms 248520 KB Output is correct
14 Correct 703 ms 251316 KB Output is correct
15 Correct 530 ms 250532 KB Output is correct
16 Correct 686 ms 278616 KB Output is correct
17 Correct 672 ms 251320 KB Output is correct
18 Correct 379 ms 90216 KB Output is correct
19 Correct 273 ms 90476 KB Output is correct
20 Correct 283 ms 93808 KB Output is correct
21 Correct 296 ms 90736 KB Output is correct
22 Correct 6753 ms 255252 KB Output is correct
23 Execution timed out 8073 ms 253900 KB Time limit exceeded
24 Halted 0 ms 0 KB -