Submission #852459

#	Time	Username	Problem	Language	Result	Execution time	Memory
852459		epicci23	Factories (JOI14_factories)	C++17	100 / 100	3790 ms	184496 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67