oj.uz

Submission #1051130

# Submission time Handle Problem Language Result Execution time Memory
1051130 2024-08-09T20:35:14 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278680 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 = 700 , 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 45660 KB Output is correct
2 Correct 1305 ms 52224 KB Output is correct
3 Correct 1201 ms 52304 KB Output is correct
4 Correct 1441 ms 52304 KB Output is correct
5 Correct 1309 ms 52732 KB Output is correct
6 Correct 1231 ms 52592 KB Output is correct
7 Correct 1202 ms 52308 KB Output is correct
8 Correct 338 ms 52580 KB Output is correct
9 Correct 1294 ms 52736 KB Output is correct
10 Correct 1264 ms 52704 KB Output is correct
11 Correct 1192 ms 52220 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 671 ms 248504 KB Output is correct
3 Correct 711 ms 251320 KB Output is correct
4 Correct 525 ms 250532 KB Output is correct
5 Correct 703 ms 278680 KB Output is correct
6 Correct 676 ms 251380 KB Output is correct
7 Correct 382 ms 90308 KB Output is correct
8 Correct 284 ms 90476 KB Output is correct
9 Correct 283 ms 93800 KB Output is correct
10 Correct 301 ms 90716 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 45660 KB Output is correct
2 Correct 1305 ms 52224 KB Output is correct
3 Correct 1201 ms 52304 KB Output is correct
4 Correct 1441 ms 52304 KB Output is correct
5 Correct 1309 ms 52732 KB Output is correct
6 Correct 1231 ms 52592 KB Output is correct
7 Correct 1202 ms 52308 KB Output is correct
8 Correct 338 ms 52580 KB Output is correct
9 Correct 1294 ms 52736 KB Output is correct
10 Correct 1264 ms 52704 KB Output is correct
11 Correct 1192 ms 52220 KB Output is correct
12 Correct 6 ms 45660 KB Output is correct
13 Correct 671 ms 248504 KB Output is correct
14 Correct 711 ms 251320 KB Output is correct
15 Correct 525 ms 250532 KB Output is correct
16 Correct 703 ms 278680 KB Output is correct
17 Correct 676 ms 251380 KB Output is correct
18 Correct 382 ms 90308 KB Output is correct
19 Correct 284 ms 90476 KB Output is correct
20 Correct 283 ms 93800 KB Output is correct
21 Correct 301 ms 90716 KB Output is correct
22 Correct 7017 ms 255224 KB Output is correct
23 Execution timed out 8077 ms 253668 KB Time limit exceeded
24 Halted 0 ms 0 KB -