제출 #1286420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286420		Faisal_Saqib	공장들 (JOI14_factories)	C++20	100 / 100	5350 ms	282436 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];
bool iny[KP];
vector<pair<ll,ll>> ma[KP];
ll h[KP],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);
    }
  }
}
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<<"ORD: ";
  // for(auto x:ord)cout<<x<<' ';
  // cout<<endl;
  // cout<<"Hei: ";
  for(ll i=0;i<ord.size();i++)
  {
    mi[i][0]=h[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
}
ll dist(ll x,ll y)
{
  if(x>y)swap(x,y);
  // [x,y]
  ll lp=__lg(y-x+1);
  return min(mi[x][lp],mi[y-(1<<lp)+1][lp]);
}
const ll SQT=707;
ll d[KP];
long long Query(int S, int X[], int T, int Y[]) {
  ll ans=1e18;
  if(S<SQT)
  { // SQT * 1e6 
    for(ll i=0;i<S;i++)
    {
      ll x=X[i];
      for(ll j=0;j<T;j++)
      {
        ll y=Y[j];
        ans=min(ans,h[x]+h[y]-2*dist(in[x],in[y]));
      }
    }
  }
  else
  { // n * lg n * 1e6/SQT
    // multi-source Dykstra
    // O(2nlgn)
    priority_queue<pair<ll,ll>> pq;
    for(ll i=0;i<n;i++)
    {
      d[i]=1e18;
      iny[i]=0;
    }
    for(ll i=0;i<T;i++)
    {
      iny[Y[i]]=1;
    }
    for(ll i=0;i<S;i++)
    {
        d[X[i]]=0;
        pq.push({0,X[i]});
    }
    while(pq.size())
    {
      auto it=pq.top();
      pq.pop();
      ll x=it.second;
      ll dt=it.first;
      if(iny[x])
      {
        return -dt;
      }
      if(-dt!=d[x])continue;
      for(auto y:ma[x])
      {
        ll yp=y.second,w=y.first;
        if(d[yp]>(w-dt))
        {
          d[yp]=w-dt;
          pq.push({dt-w,yp});
        }
      }
    }
  }
  return ans;
}

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