oj.uz

Submission #792171

# Submission time Handle Problem Language Result Execution time Memory
792171 2023-07-24T16:56:38 Z bane Factories (JOI14_factories) C++17
100 / 100
 4800 ms 269096 KB 
   #include<bits/stdc++.h>
    using namespace std;
    #include "factories.h"
     
    struct weighted_graph{
      long long N;
      vector<vector<pair<long long,long long>>>adj, GC;
      vector<long long>in, depth, crnci, dist, dp, sz;
      vector<vector<long long>>lift;
      inline void dec(long long _N){
        N = _N;
        adj.resize(N+1);
        in.resize(N+1);
        lift.resize(N+1);
        depth.resize(N+1);
        crnci.resize(N+1);
        dist.resize(N+1);
        GC.resize(N+1);
        dp.resize(N+1);
        sz.resize(N+1);
        for (long long i = 1; i <= N; i++){
          dp[i] = 0;
        }
        for (long long i = 1; i <= N; i++){
          lift[i].resize(20);
        }
      }   
     
      inline void add_edge(long long A, long long B, long long D){
        adj[A].push_back({B,D});
        adj[B].push_back({A,D});
      }
     
      inline void init(){
        long long timer = 1;
        function<long long(long long,long long, long long h)>Dfs = [&](long long u, long long p, long long h){
          in[u] = timer++;
          depth[u] = depth[p] + 1;
          sz[u] = 1;
          dist[u] = h;
          lift[u][0] = p;
          for (auto& [x,w] : adj[u]){
            if (x == p)continue;
            sz[u] += Dfs(x,u, h + w);
          }
          return sz[u];
        };
        depth[1] = -1;
        Dfs(1,1,0);
        for (long long i = 1; i < 20; i++){
          for (long long j = 1; j <= N; j++){
            lift[j][i] = lift[lift[j][i-1]][i-1];
          }
        }
      }
     
      inline long long LCA(long long A, long long B){
        if (depth[A] > depth[B])swap(A,B);
        long long k = depth[B] - depth[A];
        for (long long i = 19; i>=0; i--){
          if ((1 << i) & k){
            B = lift[B][i];
          }
        }
        if (A == B)
          return A;
        
        for (long long i = 19; i>=0; i--){
          if (lift[B][i] != lift[A][i]){
            B = lift[B][i];
            A = lift[A][i];
          }
        }
        return lift[A][0];
      }
     
      inline long long Dijkstra(vector<long long>& sve){
        priority_queue<pair<long long,long long>>pq;
        for (long long i = 0; i < (long long)sve.size(); i++){
          if (crnci[sve[i]] == 2){
            pq.push({0,sve[i]});
          }
        }
     
        while(!pq.empty()){
          long long node = pq.top().second;
          long long dst = -pq.top().first;
          //cout << node << " " << dst << endl;
          pq.pop();
          if (crnci[node] == 1)return dst;
          dp[node] = 1;
          for (auto& [x,w] : GC[node]){
            if (dp[x] == 0){
              pq.push({-w-dst, x});
            }
          }
        }
        return -1;
      }
     
      inline long long Query(int S, int X[], int T, int Y[]){
        vector<long long>sve;
        for (long long i = 0; i < S; i++)X[i]++;
        for (long long i = 0; i < T; i++)Y[i]++;
        for (long long i = 0; i < S; i++){
          sve.push_back(X[i]);
        }
        for (long long i = 0; i < T; i++){
          sve.push_back(Y[i]);
        }
     
        sort(sve.begin(),sve.end(), [&](long long u, long long p){
          return in[u] < in[p];
        });
     
        for (long long i = 1; i < S + T; i++){
          sve.push_back(LCA(sve[i - 1], sve[i]));
        }
        sort(sve.begin(),sve.end(), [&](long long u, long long p){
          return in[u] < in[p];
        });
        sve.erase(unique(sve.begin(),sve.end()), sve.end());
        long long where = 0;
        function<void()>build = [&](){
          long long cp = sve[where];
          where++;
          long long max_ind = in[cp] + sz[cp] - 1;
          while(where < sve.size() && in[sve[where]] <= max_ind){
              GC[cp].push_back({sve[where], dist[sve[where]] - dist[cp]});
              GC[sve[where]].push_back({cp,dist[sve[where]] - dist[cp]});
              build();
          }
        };
        build();
     
     
       //for (long long i : sve)cout << " " << i;
       // cout << endl;
     
        for (long long i = 0; i < T; i++){
          crnci[Y[i]] = 1;
        }
     
        for (long long i = 0; i < S; i++){
          crnci[X[i]] = 2;
        }
     
        long long ans = Dijkstra(sve);
     
        for (long long i = 0; i < T; i++){
          crnci[Y[i]] = 0;
        }
     
        for (long long i = 0; i < S; i++){
          crnci[X[i]] = 0;
        }
        for (long long i = 0; i < (long long)sve.size(); i++){
          GC[sve[i]].clear();
          dp[sve[i]] = 0;
        }
        return ans;
      }
     
    } G;
     
    void Init(int N, int A[], int B[], int D[]) {
      G.dec(N);
      for (int i = 0; i < N - 1; i++){
        G.add_edge(++A[i],++B[i],D[i]);
      }
      G.init();
     
    }
     
    long long Query(int S, int X[], int T, int Y[]) {
      return G.Query(S,X,T,Y);
    }

Compilation message

factories.cpp: In lambda function:
factories.cpp:128:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |           while(where < sve.size() && in[sve[where]] <= max_ind){
      |                 ~~~~~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 724 KB Output is correct
2 Correct 738 ms 10444 KB Output is correct
3 Correct 767 ms 10340 KB Output is correct
4 Correct 755 ms 10560 KB Output is correct
5 Correct 668 ms 20332 KB Output is correct
6 Correct 566 ms 20124 KB Output is correct
7 Correct 743 ms 19832 KB Output is correct
8 Correct 781 ms 19980 KB Output is correct
9 Correct 683 ms 20312 KB Output is correct
10 Correct 561 ms 20068 KB Output is correct
11 Correct 760 ms 19796 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 1986 ms 197632 KB Output is correct
3 Correct 2954 ms 221636 KB Output is correct
4 Correct 1420 ms 213476 KB Output is correct
5 Correct 2691 ms 268916 KB Output is correct
6 Correct 3362 ms 223692 KB Output is correct
7 Correct 2439 ms 63560 KB Output is correct
8 Correct 1230 ms 62460 KB Output is correct
9 Correct 1903 ms 70796 KB Output is correct
10 Correct 2067 ms 64892 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 724 KB Output is correct
2 Correct 738 ms 10444 KB Output is correct
3 Correct 767 ms 10340 KB Output is correct
4 Correct 755 ms 10560 KB Output is correct
5 Correct 668 ms 20332 KB Output is correct
6 Correct 566 ms 20124 KB Output is correct
7 Correct 743 ms 19832 KB Output is correct
8 Correct 781 ms 19980 KB Output is correct
9 Correct 683 ms 20312 KB Output is correct
10 Correct 561 ms 20068 KB Output is correct
11 Correct 760 ms 19796 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 1986 ms 197632 KB Output is correct
14 Correct 2954 ms 221636 KB Output is correct
15 Correct 1420 ms 213476 KB Output is correct
16 Correct 2691 ms 268916 KB Output is correct
17 Correct 3362 ms 223692 KB Output is correct
18 Correct 2439 ms 63560 KB Output is correct
19 Correct 1230 ms 62460 KB Output is correct
20 Correct 1903 ms 70796 KB Output is correct
21 Correct 2067 ms 64892 KB Output is correct
22 Correct 3367 ms 234920 KB Output is correct
23 Correct 3199 ms 227372 KB Output is correct
24 Correct 3605 ms 241096 KB Output is correct
25 Correct 3930 ms 236088 KB Output is correct
26 Correct 4800 ms 233176 KB Output is correct
27 Correct 3729 ms 269096 KB Output is correct
28 Correct 2356 ms 223268 KB Output is correct
29 Correct 4471 ms 231780 KB Output is correct
30 Correct 4580 ms 230772 KB Output is correct
31 Correct 4584 ms 231732 KB Output is correct
32 Correct 1763 ms 75276 KB Output is correct
33 Correct 1259 ms 71860 KB Output is correct
34 Correct 1928 ms 62088 KB Output is correct
35 Correct 1751 ms 61792 KB Output is correct
36 Correct 2087 ms 63064 KB Output is correct
37 Correct 2096 ms 62948 KB Output is correct