oj.uz

Submission #1051141

# Submission time Handle Problem Language Result Execution time Memory
1051141 2024-08-09T20:42:54 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278812 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 = 2000 , 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 45560 KB Output is correct
2 Correct 4464 ms 52376 KB Output is correct
3 Correct 1275 ms 52392 KB Output is correct
4 Correct 1452 ms 52392 KB Output is correct
5 Correct 4256 ms 52684 KB Output is correct
6 Correct 4364 ms 52308 KB Output is correct
7 Correct 1270 ms 52308 KB Output is correct
8 Correct 607 ms 52580 KB Output is correct
9 Correct 4320 ms 52564 KB Output is correct
10 Correct 4502 ms 52216 KB Output is correct
11 Correct 1213 ms 52304 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 689 ms 248340 KB Output is correct
3 Correct 744 ms 251320 KB Output is correct
4 Correct 559 ms 250528 KB Output is correct
5 Correct 762 ms 278812 KB Output is correct
6 Correct 678 ms 251380 KB Output is correct
7 Correct 397 ms 93900 KB Output is correct
8 Correct 304 ms 94316 KB Output is correct
9 Correct 289 ms 95336 KB Output is correct
10 Correct 291 ms 94404 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45560 KB Output is correct
2 Correct 4464 ms 52376 KB Output is correct
3 Correct 1275 ms 52392 KB Output is correct
4 Correct 1452 ms 52392 KB Output is correct
5 Correct 4256 ms 52684 KB Output is correct
6 Correct 4364 ms 52308 KB Output is correct
7 Correct 1270 ms 52308 KB Output is correct
8 Correct 607 ms 52580 KB Output is correct
9 Correct 4320 ms 52564 KB Output is correct
10 Correct 4502 ms 52216 KB Output is correct
11 Correct 1213 ms 52304 KB Output is correct
12 Correct 6 ms 45660 KB Output is correct
13 Correct 689 ms 248340 KB Output is correct
14 Correct 744 ms 251320 KB Output is correct
15 Correct 559 ms 250528 KB Output is correct
16 Correct 762 ms 278812 KB Output is correct
17 Correct 678 ms 251380 KB Output is correct
18 Correct 397 ms 93900 KB Output is correct
19 Correct 304 ms 94316 KB Output is correct
20 Correct 289 ms 95336 KB Output is correct
21 Correct 291 ms 94404 KB Output is correct
22 Execution timed out 8006 ms 255300 KB Time limit exceeded
23 Halted 0 ms 0 KB -