Submission #796847

#	Time	Username	Problem	Language	Result	Execution time	Memory
796847		bane	Factories (JOI14_factories)	C++17	100 / 100	5814 ms	291772 KiB

factories

       #include<bits/stdc++.h>
        using namespace std;
        #include "factories.h"
         #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
        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 (stderr)

factories.cpp: In lambda function:
factories.cpp:130:27: 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]
  130 |               while(where < sve.size() && in[sve[where]] <= max_ind){
      |                     ~~~~~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67