oj.uz

Submission #792155

# Submission time Handle Problem Language Result Execution time Memory
792155 2023-07-24T16:29:50 Z bane Factories (JOI14_factories) C++17
0 / 100
 2759 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
#include "factories.h"

struct weighted_graph{
  int N;
  vector<vector<pair<int,int>>>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] = (long long)1e18;
    }
    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){
        dp[sve[i]] = 0;
        pq.push({0,sve[i]});
      }
    }

    while(!pq.empty()){
      int node = pq.top().second;
      long long dst = -pq.top().first;
      pq.pop();
      if (dst != dp[node])continue;
      if (crnci[node] == 1)return dst;
      for (auto& [x,w] : GC[node]){
        if (dp[x] > w + dst){
          dp[x] = w + dst;
          pq.push({-dp[x], 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]] = (long long)1e18;
    }
    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:129:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |       while(where < sve.size() && in[sve[where]] <= max_ind){
      |             ~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 852 KB Output is correct
2 Correct 748 ms 19284 KB Output is correct
3 Correct 763 ms 19232 KB Output is correct
4 Runtime error 2759 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Incorrect 2097 ms 170144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 852 KB Output is correct
2 Correct 748 ms 19284 KB Output is correct
3 Correct 763 ms 19232 KB Output is correct
4 Runtime error 2759 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -