oj.uz

Submission #852459

# Submission time Handle Problem Language Result Execution time Memory
852459 2023-09-21T20:16:31 Z epicci23 Factories (JOI14_factories) C++17
100 / 100
 3790 ms 184496 KB 
#include "bits/stdc++.h"
#include "factories.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int N = 5e5 + 5;
const int LOG = 30;
const long long INF = 1e18;
vector<array<long long,2>> v[N];  
int tin[N],tout[N];
long long depth[N];
int t=0;
int lift[N][LOG];


void dfs(int c,int p,long long d){
    depth[c]=d;
    tin[c]=t++;
    tout[c]=tin[c];
    lift[c][0]=p;
    for(int i=1;i<LOG;i++) lift[c][i]=lift[lift[c][i-1]][i-1];
    for(auto x:v[c]){
      if(x[0]==p) continue;
      dfs(x[0],c,d+x[1]);
      tout[c]=max(tout[c],tout[x[0]]);
    }
}

  bool check(int a,int b){
    return tin[a] <= tin[b] && tin[b]<=tout[a];
  }

  int lca(int a,int b){
    if(check(a,b)) return a;
    for(int i=LOG-1;i>=0;i--){
      if(!check(lift[a][i],b)) a=lift[a][i];
    }
    return lift[a][0];
  }

  void Init(int N, int A[], int B[], int D[]) {
    for(int i=0;i<N-1;i++){
      v[A[i]].pb({B[i],D[i]});
      v[B[i]].pb({A[i],D[i]});
    }
    dfs(0,0,0);
  }

  long long Query(int S, int X[], int T, int Y[]){
    
    long long ans=INF;
    vector<pair<int,int>> cur;
    for(int i=0;i<S;i++) cur.pb({X[i],0});
    for(int i=0;i<T;i++) cur.pb({Y[i],1});

    map<int,int> vis;
    for(int i=0;i<sz(cur);i++) vis[cur[i].first]=1;

    sort(cur.begin(),cur.end(),[&](pair<int,int> i,pair<int,int> j){
      return tin[i.first] < tin[j.first];
    });

    vector<pair<int,int>> todo;

    for(int i=1;i<sz(cur);i++){
      if(!vis[lca(cur[i-1].first,cur[i].first)]){
       todo.pb({lca(cur[i-1].first,cur[i].first),2});
       vis[lca(cur[i-1].first,cur[i].first)]=1;
      }
    }

    for(auto x:todo) cur.pb(x);

    sort(cur.begin(),cur.end(),[&](pair<int,int> i,pair<int,int> j){
      return tin[i.first] < tin[j.first];
    });

    cur.erase(unique(cur.begin(), cur.end()),cur.end());

    vector<pair<int,long long>> g2[sz(cur) + 5];
    array<long long,2> dp[sz(cur)+5];
    
    for(int i=0;i<sz(cur)+5;i++) dp[i]={INF,INF};

    stack<int> s;
    s.push(0);
    for(int i=1;i<(int)cur.size();i++){
      int c = cur[i].first;
      while(!check(cur[s.top()].first,c)) s.pop();
      g2[s.top()].pb({i,depth[c]-depth[cur[s.top()].first]});
      s.push(i);
    }

    for(int i=sz(cur)-1;i>=0;i--){

      if(cur[i].second==0) dp[i][0]=depth[cur[i].first];
      else if(cur[i].second==1) dp[i][1]=depth[cur[i].first];

      for(auto x:g2[i]){
        dp[i][0]=min(dp[i][0],dp[x.first][0]);
        dp[i][1]=min(dp[i][1],dp[x.first][1]);
      }

      //cout << "i: " << cur[i].first << " " << dp[i][0] << " " << dp[i][1] << endl;
      if(dp[i][0]!=INF && dp[i][1]!=INF) ans=min(ans,dp[i][0]+dp[i][1]-depth[cur[i].first]*2);
    }

    return ans;
  }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35416 KB Output is correct
2 Correct 1401 ms 51756 KB Output is correct
3 Correct 1692 ms 51460 KB Output is correct
4 Correct 1469 ms 52184 KB Output is correct
5 Correct 868 ms 51932 KB Output is correct
6 Correct 985 ms 51748 KB Output is correct
7 Correct 1688 ms 51544 KB Output is correct
8 Correct 1467 ms 51948 KB Output is correct
9 Correct 878 ms 51952 KB Output is correct
10 Correct 973 ms 51796 KB Output is correct
11 Correct 1711 ms 51796 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35416 KB Output is correct
2 Correct 1431 ms 146152 KB Output is correct
3 Correct 1873 ms 150584 KB Output is correct
4 Correct 925 ms 143536 KB Output is correct
5 Correct 963 ms 180624 KB Output is correct
6 Correct 1946 ms 151348 KB Output is correct
7 Correct 2043 ms 73008 KB Output is correct
8 Correct 899 ms 71680 KB Output is correct
9 Correct 672 ms 76648 KB Output is correct
10 Correct 1988 ms 73556 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35416 KB Output is correct
2 Correct 1401 ms 51756 KB Output is correct
3 Correct 1692 ms 51460 KB Output is correct
4 Correct 1469 ms 52184 KB Output is correct
5 Correct 868 ms 51932 KB Output is correct
6 Correct 985 ms 51748 KB Output is correct
7 Correct 1688 ms 51544 KB Output is correct
8 Correct 1467 ms 51948 KB Output is correct
9 Correct 878 ms 51952 KB Output is correct
10 Correct 973 ms 51796 KB Output is correct
11 Correct 1711 ms 51796 KB Output is correct
12 Correct 9 ms 35416 KB Output is correct
13 Correct 1431 ms 146152 KB Output is correct
14 Correct 1873 ms 150584 KB Output is correct
15 Correct 925 ms 143536 KB Output is correct
16 Correct 963 ms 180624 KB Output is correct
17 Correct 1946 ms 151348 KB Output is correct
18 Correct 2043 ms 73008 KB Output is correct
19 Correct 899 ms 71680 KB Output is correct
20 Correct 672 ms 76648 KB Output is correct
21 Correct 1988 ms 73556 KB Output is correct
22 Correct 3014 ms 164820 KB Output is correct
23 Correct 2802 ms 166300 KB Output is correct
24 Correct 3612 ms 166552 KB Output is correct
25 Correct 3510 ms 167156 KB Output is correct
26 Correct 3739 ms 156124 KB Output is correct
27 Correct 2299 ms 184496 KB Output is correct
28 Correct 1967 ms 163228 KB Output is correct
29 Correct 3790 ms 155396 KB Output is correct
30 Correct 3719 ms 154808 KB Output is correct
31 Correct 3651 ms 155464 KB Output is correct
32 Correct 1357 ms 83448 KB Output is correct
33 Correct 1441 ms 82700 KB Output is correct
34 Correct 2017 ms 71420 KB Output is correct
35 Correct 2008 ms 71292 KB Output is correct
36 Correct 2420 ms 72108 KB Output is correct
37 Correct 2580 ms 71984 KB Output is correct