Submission #1286927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286927		Faisal_Saqib	Factories (JOI14_factories)	C++20	100 / 100	1628 ms	464556 KiB

factories

#include "factories.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll KP=1e6+100,NP=1e6+100,lg=22;
ll n,in[KP],out[KP];
bool iny[KP],inx[KP];
vector<pair<ll,ll>> ma[KP];
ll h[KP];
pair<ll,ll> mi[NP][lg];
vector<ll> ord;
void dfs(ll x,ll p=-1)
{
  in[x]=ord.size();
  ord.push_back(x);
  for(auto y:ma[x])
  {
    if(y.second!=p)
    {
      h[y.second]=h[x]+y.first;
      dfs(y.second,x);
      ord.push_back(x);
    }
  }
  out[x]=ord.size();
}
void Init(int N, int A[], int B[], int D[]) {
  n=N;
  ord.clear();
  for(ll i=0;i<=n;i++)h[i]=0,ma[i].clear();
  for(ll i=0;i<n-1;i++)
  {
    ma[A[i]].push_back({D[i],B[i]});
    ma[B[i]].push_back({D[i],A[i]});
  }
  dfs(0);
  // cout<<"H: ";
  for(ll i=0;i<ord.size();i++)
  {
    mi[i][0]={h[ord[i]],ord[i]};
    // cout<<h[ord[i]]<<' ';
  }
  // cout<<endl;
  for(ll j=1;j<lg;j++)
  {
    for(ll i=0;i+(1<<j)-1<ord.size();i++)
    {
      mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
    }
  }
  // cout<<ord.size()<<endl;
  // ord.size() = 2*n-1
}
pair<ll,ll> getmin(ll x,ll y)
{
  if(x>y)swap(x,y);
  // [x,y]
  ll lp=__lg(y-x+1);
  // cout<<"Getting min "<<x<<' '<<y<<' '<<min(mi[x][lp],mi[y-(1<<lp)+1][lp]).second<<endl;
  return min(mi[x][lp],mi[y-(1<<lp)+1][lp]);
}
vector<pair<int,int>> cur;
ll dp[KP][2],ans=1e18;
void dfsp(int x,int p=-1)
{
  dp[x][0]=dp[x][1]=1e18;
  if(inx[x])
  {
    dp[x][0]=h[x];
    inx[x]=0;
  }
  if(iny[x])
  {
    dp[x][1]=h[x];
    iny[x]=0;
  }
  while(cur.size()>0)
  {
    int y=cur.back().second;
    if(in[x]<=in[y] and out[y]<=out[x])
    {
      cur.pop_back();
      dfsp(y,x);
      dp[x][0]=min(dp[x][0],dp[y][0]);
      dp[x][1]=min(dp[x][1],dp[y][1]);
    }
    else
    {
      break;
    }
  }
  ans=min(ans,dp[x][0]+dp[x][1]-2*h[x]);
}
long long Query(int S, int X[], int T, int Y[]) {
  cur.clear();
  ans=1e18;
  for(int i=0;i<S;i++)
  {
    inx[X[i]]=1;
    cur.push_back({in[X[i]],X[i]});
  }
  for(int i=0;i<T;i++)
  {
    iny[Y[i]]=1;
    cur.push_back({in[Y[i]],Y[i]});
  }
  sort(begin(cur),end(cur));
  // cout<<cur.size()<<endl;
  int sz=cur.size();
  for(int i=1;i<sz;i++)
  {
    // cout<<"Getting lca "<<cur[i].second<<' '<<cur[i-1].second<<' ';
    int x=getmin(in[cur[i].second],in[cur[i-1].second]).second;
    // cout<<x<<endl;
    cur.push_back({in[x],x});
  }
  sort(rbegin(cur),rend(cur));
  // do dfs using cur
  cur.resize(unique(begin(cur),end(cur))-begin(cur));
   auto y=cur.back();
  cur.pop_back();
  dfsp(y.second);
  return ans;
}

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