Submission #82877

#	Time	Username	Problem	Language	Result	Execution time	Memory
82877		Bodo171	Factories (JOI14_factories)	C++14	33 / 100	8111 ms	336988 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 tt[20][nmax];
int l[nmax],r[nmax],et[nmax];
int all[2*nmax],st[nmax];
long long ans;
int nr,i,j,n,aux,u;
bool comp(int unu,int doi)
{
    return (l[unu]<l[doi]);
}
void dfs(int x)
{
    int nod=0;
    nr++;l[x]=nr;
    for(int i=0;i<v[x].size();i++)
    {
        nod=v[x][i].first;
        if(!l[nod])
      {
        lev[nod]=lev[x]+1LL*v[x][i].second;
        tt[0][nod]=x;
        dfs(nod);
      }
    }
    r[x]=nr;
}
void deci_eram_la_un_chef()
{
    for(i=1;i<=18;i++)
        for(j=0;j<n;j++)
          tt[i][j]=tt[i-1][tt[i-1][j]];
}
bool cup(int x,int y)
{
    return (l[x]<=l[y]&&l[y]<=r[x]);
}
int lca(int A,int B)
{
    for(int p=18;p>=0;p--)
    {
        aux=tt[p][A];
        if(!(cup(aux,B)))
            A=aux;
    }
    if(!(cup(A,B)))
        A=tt[0][A];
    return A;
}
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;
}

Compilation message (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:73: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: 0 / 67