Submission #792169

# Submission time Handle Problem Language Result Execution time Memory
792169 2023-07-24T16:54:37 Z bane Factories (JOI14_factories) C++17
0 / 100
1868 ms 158540 KB
    #include<bits/stdc++.h>
    using namespace std;
    #include "factories.h"
     
    struct weighted_graph{
      int N;
      vector<vector<pair<long long,long long>>>adj, GC;
      vector<long long>in, depth, crnci, dist, dp, sz;
      vector<vector<int>>lift;
      inline void dec(int _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 (int i = 1; i <= N; i++){
          dp[i] = 0;
        }
        for (int i = 1; i <= N; i++){
          lift[i].resize(20);
        }
      }   
     
      inline void add_edge(int A, int B, int D){
        adj[A].push_back({B,D});
        adj[B].push_back({A,D});
      }
     
      inline void init(){
        int timer = 1;
        function<int(int,int, long long h)>Dfs = [&](int u, int 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 (int i = 1; i < 20; i++){
          for (int j = 1; j <= N; j++){
            lift[j][i] = lift[lift[j][i-1]][i-1];
          }
        }
      }
     
      inline int LCA(int A, int B){
        if (depth[A] > depth[B])swap(A,B);
        int k = depth[B] - depth[A];
        for (int i = 19; i>=0; i--){
          if ((1 << i) & k){
            B = lift[B][i];
          }
        }
        if (A == B)
          return A;
        
        for (int 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 int Dijkstra(vector<int>& sve){
        priority_queue<pair<long long,int>>pq;
        for (int i = 0; i < (int)sve.size(); i++){
          if (crnci[sve[i]] == 2){
            pq.push({0,sve[i]});
          }
        }
     
        while(!pq.empty()){
          int 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 int Query(int S, int X[], int T, int Y[]){
        vector<int>sve;
        for (int i = 0; i < S; i++)X[i]++;
        for (int i = 0; i < T; i++)Y[i]++;
        for (int i = 0; i < S; i++){
          sve.push_back(X[i]);
        }
        for (int i = 0; i < T; i++){
          sve.push_back(Y[i]);
        }
     
        sort(sve.begin(),sve.end(), [&](int u, int p){
          return in[u] < in[p];
        });
     
        for (int i = 1; i < S + T; i++){
          sve.push_back(LCA(sve[i - 1], sve[i]));
        }
        sort(sve.begin(),sve.end(), [&](int u, int p){
          return in[u] < in[p];
        });
        sve.erase(unique(sve.begin(),sve.end()), sve.end());
        int where = 0;
        function<void()>build = [&](){
          int cp = sve[where];
          where++;
          int 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 (int i : sve)cout << " " << i;
       // cout << endl;
     
        for (int i = 0; i < T; i++){
          crnci[Y[i]] = 1;
        }
     
        for (int i = 0; i < S; i++){
          crnci[X[i]] = 2;
        }
     
        long long ans = Dijkstra(sve);
     
        for (int i = 0; i < T; i++){
          crnci[Y[i]] = 0;
        }
     
        for (int i = 0; i < S; i++){
          crnci[X[i]] = 0;
        }
        for (int i = 0; i < (int)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: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |           while(where < sve.size() && in[sve[where]] <= max_ind){
      |                 ~~~~~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 16 ms 852 KB Output is correct
2 Correct 776 ms 12320 KB Output is correct
3 Correct 760 ms 12280 KB Output is correct
4 Incorrect 788 ms 11720 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Incorrect 1868 ms 158540 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 16 ms 852 KB Output is correct
2 Correct 776 ms 12320 KB Output is correct
3 Correct 760 ms 12280 KB Output is correct
4 Incorrect 788 ms 11720 KB Output isn't correct
5 Halted 0 ms 0 KB -