oj.uz

Submission #1051137

# Submission time Handle Problem Language Result Execution time Memory
1051137 2024-08-09T20:40:01 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278720 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 = 100 , 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 15 ms 45660 KB Output is correct
2 Correct 673 ms 52428 KB Output is correct
3 Correct 1963 ms 52308 KB Output is correct
4 Correct 1378 ms 52400 KB Output is correct
5 Correct 637 ms 52736 KB Output is correct
6 Correct 622 ms 52600 KB Output is correct
7 Correct 2019 ms 52308 KB Output is correct
8 Correct 330 ms 52552 KB Output is correct
9 Correct 607 ms 52564 KB Output is correct
10 Correct 628 ms 52720 KB Output is correct
11 Correct 1940 ms 52212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 45656 KB Output is correct
2 Correct 653 ms 248504 KB Output is correct
3 Correct 709 ms 251320 KB Output is correct
4 Correct 528 ms 250656 KB Output is correct
5 Correct 694 ms 278720 KB Output is correct
6 Correct 669 ms 251480 KB Output is correct
7 Correct 386 ms 90308 KB Output is correct
8 Correct 280 ms 90476 KB Output is correct
9 Correct 277 ms 93636 KB Output is correct
10 Correct 289 ms 90792 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45660 KB Output is correct
2 Correct 673 ms 52428 KB Output is correct
3 Correct 1963 ms 52308 KB Output is correct
4 Correct 1378 ms 52400 KB Output is correct
5 Correct 637 ms 52736 KB Output is correct
6 Correct 622 ms 52600 KB Output is correct
7 Correct 2019 ms 52308 KB Output is correct
8 Correct 330 ms 52552 KB Output is correct
9 Correct 607 ms 52564 KB Output is correct
10 Correct 628 ms 52720 KB Output is correct
11 Correct 1940 ms 52212 KB Output is correct
12 Correct 6 ms 45656 KB Output is correct
13 Correct 653 ms 248504 KB Output is correct
14 Correct 709 ms 251320 KB Output is correct
15 Correct 528 ms 250656 KB Output is correct
16 Correct 694 ms 278720 KB Output is correct
17 Correct 669 ms 251480 KB Output is correct
18 Correct 386 ms 90308 KB Output is correct
19 Correct 280 ms 90476 KB Output is correct
20 Correct 277 ms 93636 KB Output is correct
21 Correct 289 ms 90792 KB Output is correct
22 Correct 6732 ms 255208 KB Output is correct
23 Execution timed out 8051 ms 253496 KB Time limit exceeded
24 Halted 0 ms 0 KB -