oj.uz

답안 #852439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852439 2023-09-21T19:40:43 Z epicci23 공장들 (JOI14_factories) C++17
0 / 100
 36 ms 35608 KB 
  #include "factories.h"
  #include "bits/stdc++.h"
  using namespace std;
  #define pb push_back
  #define sz(x) ((int)(x).size())
  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]]);
    }
  }

  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);
  }

  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];
  }


  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]={-1,-1};

    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]){
        if(dp[x.first][0]!=-1) dp[i][0]=min(dp[i][0],dp[x.first][0]+x.second);
        if(dp[x.first][1]!=-1) dp[i][1]=min(dp[i][1],dp[x.first][1]+x.second);
      }
      if(dp[i][0]!=-1 && dp[i][1]!=-1) ans=min(ans,dp[i][0]+dp[i][1]);
    }

    return ans;
  }

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 35608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 35416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 35608 KB Output isn't correct
2 Halted 0 ms 0 KB -