제출 #82880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
82880		Bodo171	공장들 (JOI14_factories)	C++14	100 / 100	4354 ms	268132 KiB

factories

#include "factories.h"
#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;
const int nmax=500005;
vector< pair<int,long long> > v[nmax];
vector<int> ad[nmax];
long long lev[nmax],mn[nmax][2];
int rmq[20][2*nmax];
int l[nmax],r[nmax],et[nmax],L[nmax],lg[2*nmax],first[nmax];
int all[2*nmax],st[nmax];
long long ans;
int nr,i,j,n,aux,u,R;
bool comp(int unu,int doi)
{
    return (l[unu]<l[doi]);
}
void dfs(int x)
{
    int nod=0;
    nr++;l[x]=nr;rmq[0][++R]=x;first[x]=R;
    for(int i=0;i<v[x].size();i++)
    {
        nod=v[x][i].first;
        if(!l[nod])
      {
        L[nod]=L[x]+1;
        lev[nod]=lev[x]+1LL*v[x][i].second;
        dfs(nod);
        rmq[0][++R]=x;
      }
    }
    r[x]=nr;
}
int minlev(int A,int B)
{
    if(L[A]<L[B]) return A;
    return B;
}
void deci_eram_la_un_chef()
{
    for(i=2;i<=2*n;i++)
        lg[i]=lg[i/2]+1;
    for(i=1;i<=19;i++)
        for(j=1;j<=R-(1<<i)+1;j++)
          rmq[i][j]=minlev(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
bool cup(int x,int y)
{
    return (l[x]<=l[y]&&l[y]<=r[x]);
}
int niv,unu,doi;
int lca(int A,int B)
{
    unu=first[A];doi=first[B];
    if(unu>doi)
        swap(unu,doi);
    niv=lg[doi-unu+1];
    return minlev(rmq[niv][unu],rmq[niv][doi-(1<<niv)+1]);
}
void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int i=0;i<N-1;i++)
    {
        v[A[i]].push_back({B[i],D[i]});
        v[B[i]].push_back({A[i],D[i]});
    }
    dfs(0);
    deci_eram_la_un_chef();
}
void defeseu(int x)
{
    int nod=0;
    if(et[x])
        mn[x][et[x]-1]=lev[x];
    for(int i=0;i<ad[x].size();i++)
    {
        nod=ad[x][i];
        defeseu(nod);
        for(int it=0;it<2;it++)
          ans=min(ans,mn[x][it]+mn[nod][1-it]-2*lev[x]);
        for(int it=0;it<2;it++)
            mn[x][it]=min(mn[x][it],mn[nod][it]);
    }
}
long long Query(int S, int X[], int T, int Y[]) {
  for(int i=0;i<S;i++)
    et[X[i]]=1;
  for(int i=0;i<T;i++)
    et[Y[i]]=2;
  sort(X,X+S,comp);sort(Y,Y+T,comp);
  merge(X,X+S,Y,Y+T,all,comp);
  nr=S+T;
  int x,y,t;
  for(i=0;i<S+T-1;i++)
  {
     x=all[i];y=all[i+1];
     t=lca(x,y);
     if(t!=x&&t!=y) all[nr++]=t;
  }
  sort(all,all+nr,comp);u=0;
  all[nr]=-1;
  for(int i=0;i<nr;i++)
     if(all[i]!=all[i+1])
  {
    while(u&&(!cup(st[u],all[i])))
        u--;
    if(u)ad[st[u]].push_back(all[i]);
    st[++u]=all[i];
    mn[all[i]][0]=mn[all[i]][1]=1LL*1e16;
  }
  ans=LLONG_MAX;
  defeseu(all[0]);
  for(int i=0;i<nr;i++)
    ad[all[i]].clear(),et[all[i]]=0;
  return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'void dfs(int)':
factories.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
factories.cpp: In function 'void defeseu(int)':
factories.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ad[x].size();i++)
                 ~^~~~~~~~~~~~~

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