Submission #1286409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286409		Faisal_Saqib	Factories (JOI14_factories)	C++20	33 / 100	8089 ms	247668 KiB

factories

#include "factories.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int KP=5e5+10,NP=1e6+10,lg=20;
int n,in[KP];
vector<pair<int,int>> ma[KP];
ll h[KP],mi[NP][lg];
vector<int> ord;
void dfs(int x,int 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);
    }
  }
}
void Init(int N, int A[], int B[], int D[]) {
  n=N;
  ord.clear();
  for(int i=0;i<=n;i++)h[i]=0,ma[i].clear();
  for(int 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<<"ORD: ";
  // for(auto x:ord)cout<<x<<' ';
  // cout<<endl;
  // cout<<"Hei: ";
  for(int i=0;i<ord.size();i++)
  {
    mi[i][0]=h[ord[i]];
    // cout<<h[ord[i]]<<' ';
  }
  // cout<<endl;
  for(int j=1;j<lg;j++)
  {
    for(int 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
}
ll dist(int x,int y)
{
  if(x>y)swap(x,y);
  // [x,y]
  int lp=__lg(y-x+1);
  return min(mi[x][lp],mi[y-(1<<lp)+1][lp]);
}
long long Query(int S, int X[], int T, int Y[]) {
  ll ans=1e18;
  for(int i=0;i<S;i++)
  {
    int x=X[i];
    for(int j=0;j<T;j++)
    {
      int y=Y[j];
      ans=min(ans,h[x]+h[y]-2*dist(in[x],in[y]));
    }
  }
  return ans;
}

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