oj.uz

Submission #1051131

# Submission time Handle Problem Language Result Execution time Memory
1051131 2024-08-09T20:35:39 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278988 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 = 800 , 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 1710 ms 34140 KB Output is correct
3 Correct 1301 ms 34028 KB Output is correct
4 Correct 1543 ms 33880 KB Output is correct
5 Correct 1577 ms 34452 KB Output is correct
6 Correct 1626 ms 34244 KB Output is correct
7 Correct 1327 ms 33940 KB Output is correct
8 Correct 355 ms 52576 KB Output is correct
9 Correct 1522 ms 52768 KB Output is correct
10 Correct 1522 ms 52636 KB Output is correct
11 Correct 1214 ms 52308 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 660 ms 248384 KB Output is correct
3 Correct 733 ms 251320 KB Output is correct
4 Correct 532 ms 250532 KB Output is correct
5 Correct 704 ms 278988 KB Output is correct
6 Correct 675 ms 251316 KB Output is correct
7 Correct 370 ms 90308 KB Output is correct
8 Correct 297 ms 90560 KB Output is correct
9 Correct 283 ms 93796 KB Output is correct
10 Correct 292 ms 90736 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 1710 ms 34140 KB Output is correct
3 Correct 1301 ms 34028 KB Output is correct
4 Correct 1543 ms 33880 KB Output is correct
5 Correct 1577 ms 34452 KB Output is correct
6 Correct 1626 ms 34244 KB Output is correct
7 Correct 1327 ms 33940 KB Output is correct
8 Correct 355 ms 52576 KB Output is correct
9 Correct 1522 ms 52768 KB Output is correct
10 Correct 1522 ms 52636 KB Output is correct
11 Correct 1214 ms 52308 KB Output is correct
12 Correct 6 ms 45656 KB Output is correct
13 Correct 660 ms 248384 KB Output is correct
14 Correct 733 ms 251320 KB Output is correct
15 Correct 532 ms 250532 KB Output is correct
16 Correct 704 ms 278988 KB Output is correct
17 Correct 675 ms 251316 KB Output is correct
18 Correct 370 ms 90308 KB Output is correct
19 Correct 297 ms 90560 KB Output is correct
20 Correct 283 ms 93796 KB Output is correct
21 Correct 292 ms 90736 KB Output is correct
22 Correct 6782 ms 255240 KB Output is correct
23 Execution timed out 8077 ms 253676 KB Time limit exceeded
24 Halted 0 ms 0 KB -