oj.uz

Submission #82880

# Submission time Handle Problem Language Result Execution time Memory
82880 2018-11-02T12:24:46 Z Bodo171 Factories (JOI14_factories) C++14
100 / 100
 4354 ms 268132 KB 
#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;
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 24568 KB Output is correct
2 Correct 880 ms 34316 KB Output is correct
3 Correct 913 ms 34536 KB Output is correct
4 Correct 942 ms 34548 KB Output is correct
5 Correct 919 ms 34704 KB Output is correct
6 Correct 647 ms 34704 KB Output is correct
7 Correct 890 ms 34760 KB Output is correct
8 Correct 876 ms 34760 KB Output is correct
9 Correct 947 ms 35016 KB Output is correct
10 Correct 660 ms 35072 KB Output is correct
11 Correct 883 ms 35428 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35428 KB Output is correct
2 Correct 1694 ms 165028 KB Output is correct
3 Correct 1980 ms 167624 KB Output is correct
4 Correct 1459 ms 167624 KB Output is correct
5 Correct 1957 ms 197060 KB Output is correct
6 Correct 2151 ms 197060 KB Output is correct
7 Correct 1299 ms 197060 KB Output is correct
8 Correct 920 ms 197060 KB Output is correct
9 Correct 1221 ms 197060 KB Output is correct
10 Correct 1566 ms 197060 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 24568 KB Output is correct
2 Correct 880 ms 34316 KB Output is correct
3 Correct 913 ms 34536 KB Output is correct
4 Correct 942 ms 34548 KB Output is correct
5 Correct 919 ms 34704 KB Output is correct
6 Correct 647 ms 34704 KB Output is correct
7 Correct 890 ms 34760 KB Output is correct
8 Correct 876 ms 34760 KB Output is correct
9 Correct 947 ms 35016 KB Output is correct
10 Correct 660 ms 35072 KB Output is correct
11 Correct 883 ms 35428 KB Output is correct
12 Correct 25 ms 35428 KB Output is correct
13 Correct 1694 ms 165028 KB Output is correct
14 Correct 1980 ms 167624 KB Output is correct
15 Correct 1459 ms 167624 KB Output is correct
16 Correct 1957 ms 197060 KB Output is correct
17 Correct 2151 ms 197060 KB Output is correct
18 Correct 1299 ms 197060 KB Output is correct
19 Correct 920 ms 197060 KB Output is correct
20 Correct 1221 ms 197060 KB Output is correct
21 Correct 1566 ms 197060 KB Output is correct
22 Correct 3877 ms 197060 KB Output is correct
23 Correct 3156 ms 197060 KB Output is correct
24 Correct 4354 ms 197060 KB Output is correct
25 Correct 4136 ms 197060 KB Output is correct
26 Correct 3776 ms 197060 KB Output is correct
27 Correct 4094 ms 201604 KB Output is correct
28 Correct 2411 ms 201604 KB Output is correct
29 Correct 3868 ms 221120 KB Output is correct
30 Correct 3619 ms 244260 KB Output is correct
31 Correct 3680 ms 268132 KB Output is correct
32 Correct 1868 ms 268132 KB Output is correct
33 Correct 1251 ms 268132 KB Output is correct
34 Correct 1653 ms 268132 KB Output is correct
35 Correct 1672 ms 268132 KB Output is correct
36 Correct 1755 ms 268132 KB Output is correct
37 Correct 1914 ms 268132 KB Output is correct