oj.uz

Submission #1051145

# Submission time Handle Problem Language Result Execution time Memory
1051145 2024-08-09T20:44:03 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278712 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 = 1500 , 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 4388 ms 52224 KB Output is correct
3 Correct 1208 ms 52308 KB Output is correct
4 Correct 1462 ms 52304 KB Output is correct
5 Correct 4240 ms 52684 KB Output is correct
6 Correct 4471 ms 52308 KB Output is correct
7 Correct 1214 ms 52192 KB Output is correct
8 Correct 419 ms 52552 KB Output is correct
9 Correct 4225 ms 52732 KB Output is correct
10 Correct 4440 ms 52404 KB Output is correct
11 Correct 1212 ms 52400 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 651 ms 248464 KB Output is correct
3 Correct 722 ms 251428 KB Output is correct
4 Correct 550 ms 250796 KB Output is correct
5 Correct 689 ms 278712 KB Output is correct
6 Correct 713 ms 251408 KB Output is correct
7 Correct 377 ms 90308 KB Output is correct
8 Correct 277 ms 90564 KB Output is correct
9 Correct 330 ms 93632 KB Output is correct
10 Correct 297 ms 90744 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 4388 ms 52224 KB Output is correct
3 Correct 1208 ms 52308 KB Output is correct
4 Correct 1462 ms 52304 KB Output is correct
5 Correct 4240 ms 52684 KB Output is correct
6 Correct 4471 ms 52308 KB Output is correct
7 Correct 1214 ms 52192 KB Output is correct
8 Correct 419 ms 52552 KB Output is correct
9 Correct 4225 ms 52732 KB Output is correct
10 Correct 4440 ms 52404 KB Output is correct
11 Correct 1212 ms 52400 KB Output is correct
12 Correct 6 ms 45656 KB Output is correct
13 Correct 651 ms 248464 KB Output is correct
14 Correct 722 ms 251428 KB Output is correct
15 Correct 550 ms 250796 KB Output is correct
16 Correct 689 ms 278712 KB Output is correct
17 Correct 713 ms 251408 KB Output is correct
18 Correct 377 ms 90308 KB Output is correct
19 Correct 277 ms 90564 KB Output is correct
20 Correct 330 ms 93632 KB Output is correct
21 Correct 297 ms 90744 KB Output is correct
22 Correct 7332 ms 255268 KB Output is correct
23 Correct 4051 ms 248780 KB Output is correct
24 Correct 6916 ms 256936 KB Output is correct
25 Correct 5139 ms 257780 KB Output is correct
26 Execution timed out 8042 ms 250036 KB Time limit exceeded
27 Halted 0 ms 0 KB -