oj.uz

Submission #1051124

# Submission time Handle Problem Language Result Execution time Memory
1051124 2024-08-09T20:29:03 Z pera Factories (JOI14_factories) C++17
33 / 100
 8000 ms 345568 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 = 1e6 + 1 , B = 500 , LOG = 20;
const long long oo = 1e16;
int T = 0 , n;
vector<int> d(MAX) , in(MAX) , order = {0};
vector<vector<int>> g(MAX);
vector<long long> D(MAX);
vector<vector<long long>> w(MAX);
vector<vector<pii>> mn(MAX , vector<pii>(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 98 ms 267092 KB Output is correct
2 Correct 1140 ms 273588 KB Output is correct
3 Correct 1583 ms 280660 KB Output is correct
4 Correct 1922 ms 280752 KB Output is correct
5 Correct 1132 ms 285008 KB Output is correct
6 Correct 1165 ms 280948 KB Output is correct
7 Correct 1562 ms 282704 KB Output is correct
8 Correct 435 ms 280912 KB Output is correct
9 Correct 1186 ms 283076 KB Output is correct
10 Correct 1096 ms 283076 KB Output is correct
11 Correct 1589 ms 282708 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 260768 KB Output is correct
2 Correct 817 ms 310288 KB Output is correct
3 Correct 888 ms 313072 KB Output is correct
4 Correct 739 ms 314416 KB Output is correct
5 Correct 830 ms 335664 KB Output is correct
6 Correct 821 ms 314100 KB Output is correct
7 Correct 640 ms 280492 KB Output is correct
8 Correct 494 ms 281500 KB Output is correct
9 Correct 453 ms 285476 KB Output is correct
10 Correct 484 ms 283184 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 267092 KB Output is correct
2 Correct 1140 ms 273588 KB Output is correct
3 Correct 1583 ms 280660 KB Output is correct
4 Correct 1922 ms 280752 KB Output is correct
5 Correct 1132 ms 285008 KB Output is correct
6 Correct 1165 ms 280948 KB Output is correct
7 Correct 1562 ms 282704 KB Output is correct
8 Correct 435 ms 280912 KB Output is correct
9 Correct 1186 ms 283076 KB Output is correct
10 Correct 1096 ms 283076 KB Output is correct
11 Correct 1589 ms 282708 KB Output is correct
12 Correct 88 ms 260768 KB Output is correct
13 Correct 817 ms 310288 KB Output is correct
14 Correct 888 ms 313072 KB Output is correct
15 Correct 739 ms 314416 KB Output is correct
16 Correct 830 ms 335664 KB Output is correct
17 Correct 821 ms 314100 KB Output is correct
18 Correct 640 ms 280492 KB Output is correct
19 Correct 494 ms 281500 KB Output is correct
20 Correct 453 ms 285476 KB Output is correct
21 Correct 484 ms 283184 KB Output is correct
22 Correct 7271 ms 345568 KB Output is correct
23 Execution timed out 8055 ms 344484 KB Time limit exceeded
24 Halted 0 ms 0 KB -