oj.uz

Submission #1051135

# Submission time Handle Problem Language Result Execution time Memory
1051135 2024-08-09T20:38:42 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278716 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 = 200 , 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 45796 KB Output is correct
2 Correct 669 ms 52472 KB Output is correct
3 Correct 1549 ms 52304 KB Output is correct
4 Correct 1205 ms 52228 KB Output is correct
5 Correct 630 ms 52724 KB Output is correct
6 Correct 667 ms 52600 KB Output is correct
7 Correct 1194 ms 52400 KB Output is correct
8 Correct 332 ms 52572 KB Output is correct
9 Correct 637 ms 52560 KB Output is correct
10 Correct 628 ms 52596 KB Output is correct
11 Correct 1202 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 647 ms 248400 KB Output is correct
3 Correct 733 ms 251456 KB Output is correct
4 Correct 547 ms 250524 KB Output is correct
5 Correct 697 ms 278716 KB Output is correct
6 Correct 663 ms 251320 KB Output is correct
7 Correct 355 ms 90308 KB Output is correct
8 Correct 298 ms 90564 KB Output is correct
9 Correct 311 ms 93800 KB Output is correct
10 Correct 303 ms 90820 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45796 KB Output is correct
2 Correct 669 ms 52472 KB Output is correct
3 Correct 1549 ms 52304 KB Output is correct
4 Correct 1205 ms 52228 KB Output is correct
5 Correct 630 ms 52724 KB Output is correct
6 Correct 667 ms 52600 KB Output is correct
7 Correct 1194 ms 52400 KB Output is correct
8 Correct 332 ms 52572 KB Output is correct
9 Correct 637 ms 52560 KB Output is correct
10 Correct 628 ms 52596 KB Output is correct
11 Correct 1202 ms 52396 KB Output is correct
12 Correct 6 ms 45660 KB Output is correct
13 Correct 647 ms 248400 KB Output is correct
14 Correct 733 ms 251456 KB Output is correct
15 Correct 547 ms 250524 KB Output is correct
16 Correct 697 ms 278716 KB Output is correct
17 Correct 663 ms 251320 KB Output is correct
18 Correct 355 ms 90308 KB Output is correct
19 Correct 298 ms 90564 KB Output is correct
20 Correct 311 ms 93800 KB Output is correct
21 Correct 303 ms 90820 KB Output is correct
22 Correct 7122 ms 255284 KB Output is correct
23 Execution timed out 8080 ms 253548 KB Time limit exceeded
24 Halted 0 ms 0 KB -