oj.uz

Submission #1051140

# Submission time Handle Problem Language Result Execution time Memory
1051140 2024-08-09T20:41:36 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 282444 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 = 1000 , 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 45656 KB Output is correct
2 Correct 2090 ms 52424 KB Output is correct
3 Correct 1216 ms 52388 KB Output is correct
4 Correct 1400 ms 52212 KB Output is correct
5 Correct 2140 ms 52732 KB Output is correct
6 Correct 2068 ms 52580 KB Output is correct
7 Correct 1205 ms 52400 KB Output is correct
8 Correct 377 ms 52580 KB Output is correct
9 Correct 2214 ms 52728 KB Output is correct
10 Correct 2050 ms 52584 KB Output is correct
11 Correct 1254 ms 52396 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 654 ms 248388 KB Output is correct
3 Correct 723 ms 251460 KB Output is correct
4 Correct 558 ms 250512 KB Output is correct
5 Correct 685 ms 278716 KB Output is correct
6 Correct 695 ms 251576 KB Output is correct
7 Correct 413 ms 92000 KB Output is correct
8 Correct 303 ms 92264 KB Output is correct
9 Correct 284 ms 97448 KB Output is correct
10 Correct 329 ms 92484 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 45656 KB Output is correct
2 Correct 2090 ms 52424 KB Output is correct
3 Correct 1216 ms 52388 KB Output is correct
4 Correct 1400 ms 52212 KB Output is correct
5 Correct 2140 ms 52732 KB Output is correct
6 Correct 2068 ms 52580 KB Output is correct
7 Correct 1205 ms 52400 KB Output is correct
8 Correct 377 ms 52580 KB Output is correct
9 Correct 2214 ms 52728 KB Output is correct
10 Correct 2050 ms 52584 KB Output is correct
11 Correct 1254 ms 52396 KB Output is correct
12 Correct 6 ms 45660 KB Output is correct
13 Correct 654 ms 248388 KB Output is correct
14 Correct 723 ms 251460 KB Output is correct
15 Correct 558 ms 250512 KB Output is correct
16 Correct 685 ms 278716 KB Output is correct
17 Correct 695 ms 251576 KB Output is correct
18 Correct 413 ms 92000 KB Output is correct
19 Correct 303 ms 92264 KB Output is correct
20 Correct 284 ms 97448 KB Output is correct
21 Correct 329 ms 92484 KB Output is correct
22 Correct 7314 ms 255288 KB Output is correct
23 Correct 3928 ms 248760 KB Output is correct
24 Correct 6428 ms 281188 KB Output is correct
25 Correct 5223 ms 282444 KB Output is correct
26 Execution timed out 8103 ms 274496 KB Time limit exceeded
27 Halted 0 ms 0 KB -