oj.uz

답안 #1051126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1051126 2024-08-09T20:30:25 Z pera 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 334100 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 = 700 , 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

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 265044 KB Output is correct
2 Correct 1633 ms 271188 KB Output is correct
3 Correct 1610 ms 273236 KB Output is correct
4 Correct 1863 ms 271184 KB Output is correct
5 Correct 1590 ms 271544 KB Output is correct
6 Correct 1715 ms 271484 KB Output is correct
7 Correct 1606 ms 273328 KB Output is correct
8 Correct 448 ms 273652 KB Output is correct
9 Correct 1601 ms 273744 KB Output is correct
10 Correct 1580 ms 273536 KB Output is correct
11 Correct 1575 ms 273488 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 262852 KB Output is correct
2 Correct 808 ms 311996 KB Output is correct
3 Correct 940 ms 313008 KB Output is correct
4 Correct 678 ms 312872 KB Output is correct
5 Correct 829 ms 334100 KB Output is correct
6 Correct 841 ms 314296 KB Output is correct
7 Correct 595 ms 280816 KB Output is correct
8 Correct 444 ms 281644 KB Output is correct
9 Correct 440 ms 283936 KB Output is correct
10 Correct 475 ms 283332 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 265044 KB Output is correct
2 Correct 1633 ms 271188 KB Output is correct
3 Correct 1610 ms 273236 KB Output is correct
4 Correct 1863 ms 271184 KB Output is correct
5 Correct 1590 ms 271544 KB Output is correct
6 Correct 1715 ms 271484 KB Output is correct
7 Correct 1606 ms 273328 KB Output is correct
8 Correct 448 ms 273652 KB Output is correct
9 Correct 1601 ms 273744 KB Output is correct
10 Correct 1580 ms 273536 KB Output is correct
11 Correct 1575 ms 273488 KB Output is correct
12 Correct 91 ms 262852 KB Output is correct
13 Correct 808 ms 311996 KB Output is correct
14 Correct 940 ms 313008 KB Output is correct
15 Correct 678 ms 312872 KB Output is correct
16 Correct 829 ms 334100 KB Output is correct
17 Correct 841 ms 314296 KB Output is correct
18 Correct 595 ms 280816 KB Output is correct
19 Correct 444 ms 281644 KB Output is correct
20 Correct 440 ms 283936 KB Output is correct
21 Correct 475 ms 283332 KB Output is correct
22 Correct 7121 ms 321404 KB Output is correct
23 Execution timed out 8090 ms 319932 KB Time limit exceeded
24 Halted 0 ms 0 KB -