oj.uz

Submission #1051134

# Submission time Handle Problem Language Result Execution time Memory
1051134 2024-08-09T20:38:03 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278600 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 14 ms 45656 KB Output is correct
2 Correct 1585 ms 52224 KB Output is correct
3 Correct 1191 ms 52304 KB Output is correct
4 Correct 1503 ms 52388 KB Output is correct
5 Correct 1522 ms 52748 KB Output is correct
6 Correct 1476 ms 52584 KB Output is correct
7 Correct 1205 ms 52304 KB Output is correct
8 Correct 359 ms 52580 KB Output is correct
9 Correct 1521 ms 52728 KB Output is correct
10 Correct 1429 ms 52736 KB Output is correct
11 Correct 1197 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 674 ms 248404 KB Output is correct
3 Correct 694 ms 251220 KB Output is correct
4 Correct 535 ms 250684 KB Output is correct
5 Correct 689 ms 278600 KB Output is correct
6 Correct 668 ms 251464 KB Output is correct
7 Correct 363 ms 90228 KB Output is correct
8 Correct 297 ms 90552 KB Output is correct
9 Correct 279 ms 93804 KB Output is correct
10 Correct 304 ms 90824 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 45656 KB Output is correct
2 Correct 1585 ms 52224 KB Output is correct
3 Correct 1191 ms 52304 KB Output is correct
4 Correct 1503 ms 52388 KB Output is correct
5 Correct 1522 ms 52748 KB Output is correct
6 Correct 1476 ms 52584 KB Output is correct
7 Correct 1205 ms 52304 KB Output is correct
8 Correct 359 ms 52580 KB Output is correct
9 Correct 1521 ms 52728 KB Output is correct
10 Correct 1429 ms 52736 KB Output is correct
11 Correct 1197 ms 52400 KB Output is correct
12 Correct 6 ms 45656 KB Output is correct
13 Correct 674 ms 248404 KB Output is correct
14 Correct 694 ms 251220 KB Output is correct
15 Correct 535 ms 250684 KB Output is correct
16 Correct 689 ms 278600 KB Output is correct
17 Correct 668 ms 251464 KB Output is correct
18 Correct 363 ms 90228 KB Output is correct
19 Correct 297 ms 90552 KB Output is correct
20 Correct 279 ms 93804 KB Output is correct
21 Correct 304 ms 90824 KB Output is correct
22 Correct 6722 ms 255216 KB Output is correct
23 Execution timed out 8048 ms 253856 KB Time limit exceeded
24 Halted 0 ms 0 KB -