oj.uz

Submission #796847

# Submission time Handle Problem Language Result Execution time Memory
796847 2023-07-28T20:42:39 Z bane Factories (JOI14_factories) C++17
100 / 100
 5814 ms 291772 KB 
       #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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 980 KB Output is correct
2 Correct 1358 ms 19860 KB Output is correct
3 Correct 1277 ms 19844 KB Output is correct
4 Correct 1337 ms 20020 KB Output is correct
5 Correct 1213 ms 20568 KB Output is correct
6 Correct 1068 ms 20144 KB Output is correct
7 Correct 1243 ms 19828 KB Output is correct
8 Correct 1368 ms 20092 KB Output is correct
9 Correct 1214 ms 20552 KB Output is correct
10 Correct 1076 ms 20096 KB Output is correct
11 Correct 1248 ms 19988 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 580 KB Output is correct
2 Correct 2407 ms 216276 KB Output is correct
3 Correct 3634 ms 224296 KB Output is correct
4 Correct 1716 ms 213352 KB Output is correct
5 Correct 3773 ms 289156 KB Output is correct
6 Correct 4003 ms 226152 KB Output is correct
7 Correct 2694 ms 64112 KB Output is correct
8 Correct 1654 ms 62680 KB Output is correct
9 Correct 2476 ms 73148 KB Output is correct
10 Correct 2729 ms 65356 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 980 KB Output is correct
2 Correct 1358 ms 19860 KB Output is correct
3 Correct 1277 ms 19844 KB Output is correct
4 Correct 1337 ms 20020 KB Output is correct
5 Correct 1213 ms 20568 KB Output is correct
6 Correct 1068 ms 20144 KB Output is correct
7 Correct 1243 ms 19828 KB Output is correct
8 Correct 1368 ms 20092 KB Output is correct
9 Correct 1214 ms 20552 KB Output is correct
10 Correct 1076 ms 20096 KB Output is correct
11 Correct 1248 ms 19988 KB Output is correct
12 Correct 4 ms 580 KB Output is correct
13 Correct 2407 ms 216276 KB Output is correct
14 Correct 3634 ms 224296 KB Output is correct
15 Correct 1716 ms 213352 KB Output is correct
16 Correct 3773 ms 289156 KB Output is correct
17 Correct 4003 ms 226152 KB Output is correct
18 Correct 2694 ms 64112 KB Output is correct
19 Correct 1654 ms 62680 KB Output is correct
20 Correct 2476 ms 73148 KB Output is correct
21 Correct 2729 ms 65356 KB Output is correct
22 Correct 4525 ms 234936 KB Output is correct
23 Correct 4177 ms 234056 KB Output is correct
24 Correct 4661 ms 242988 KB Output is correct
25 Correct 4889 ms 244864 KB Output is correct
26 Correct 5514 ms 235660 KB Output is correct
27 Correct 4872 ms 291772 KB Output is correct
28 Correct 3084 ms 234144 KB Output is correct
29 Correct 5814 ms 233848 KB Output is correct
30 Correct 5807 ms 232444 KB Output is correct
31 Correct 5785 ms 233848 KB Output is correct
32 Correct 2504 ms 78216 KB Output is correct
33 Correct 1826 ms 71848 KB Output is correct
34 Correct 2544 ms 62128 KB Output is correct
35 Correct 2470 ms 61880 KB Output is correct
36 Correct 2633 ms 63524 KB Output is correct
37 Correct 2749 ms 63340 KB Output is correct