Submission #111602

#	Time	Username	Problem	Language	Result	Execution time	Memory
111602		discoverMeMe	Factories (JOI14_factories)	C++14	100 / 100	6489 ms	173936 KiB

factories

#include <bits/stdc++.h>
//#include "factories.h"
#define fori(a,b) for(int i=a;i<b;++i)
#define forj(a,b) for(int j=a;j<b;++j)
#define fork(a,b) for(int k=a;k<b;++k)

using namespace std;
const int N=500000;

int par[N],sz[N],lvl[N],V,x,y,z,l,tot;
long long ans[N],cd[N][19],xx,MAX=LLONG_MAX>>2;
vector<int> gr[N],dist[N];
bool blc[N];

int sizedfs(int v,int p)
{
    sz[v]=1;
    fori(0,gr[v].size())
        if(!blc[gr[v][i]]&&gr[v][i]!=p)
            sz[v]+=sizedfs(gr[v][i],v);
    return sz[v];
}

int getCenter(int v,int p)
{
    fori(0,gr[v].size())
        if(sz[gr[v][i]]>tot&&!blc[gr[v][i]]&&gr[v][i]!=p)
            return getCenter(gr[v][i],v);
    blc[v]=true;
    return v;
}

void dfs(int v,int p)
{
    fori(0,gr[v].size())
        if(!blc[gr[v][i]]&&gr[v][i]!=p)
        {
            cd[gr[v][i]][l]=cd[v][l]+dist[v][i];
            dfs(gr[v][i],v);
        }
}

void build(int v,int p)
{
    sizedfs(v,-1); tot=(sz[v]-1)>>1;
    v=getCenter(v,-1);
    par[v]=p; lvl[v]=l; cd[v][l]=0;
    dfs(v,-1);
    fori(0,gr[v].size())
        if(!blc[gr[v][i]])
        {
            l++;
            build(gr[v][i],v);
            l--;
        }
}

void Init(int n,int a[],int b[],int d[])
{
    V=n;
    fori(0,V)
        forj(0,19)
            cd[i][j]=MAX;
    fori(0,V-1)
    {
        gr[a[i]].push_back(b[i]); gr[b[i]].push_back(a[i]);
        dist[a[i]].push_back(d[i]); dist[b[i]].push_back(d[i]);
    }
    if(V>250000)
        build(240600,-1);
    else
        build(0,-1);
    fori(0,V)
        ans[i]=MAX;
}
long long Query(int s,int a[],int t,int b[])
{
    xx=MAX;
    if(s+t>=V)
        return 0;
    fori(0,t)
    {
        x=b[i];
        while(x!=-1)
        {
            ans[x]=min(ans[x],cd[b[i]][lvl[x]]);
            x=par[x];
        }
    }
    fori(0,s)
    {
        x=a[i];
        while(x!=-1)
        {
            xx=min(xx,ans[x]+cd[a[i]][lvl[x]]);
            x=par[x];
        }
    }
    fori(0,t)
    {
        x=b[i];
        while(x!=-1&&ans[x]!=MAX)
        {
            ans[x]=MAX;
            x=par[x];
        }
    }
    return xx;
}
/*
int a[N],b[N],c[N],aa[N],bb[N];

int main()
{
    cin.sync_with_stdio(0);
    cin.tie(0);
    freopen("02-05.txt", "r", stdin);
    int q;
    cin>>V>>q;
    fori(0,V-1)
    {
        cin>>a[i]>>b[i]>>c[i];
    }
    Init(V,a,b,c);
    forj(0,q)
    {
        cin>>x>>y;
        fori(0,x)
            cin>>aa[i];
        fori(0,y)
            cin>>bb[i];
        cout<<Query(x,aa,y,bb)<<"\n";
    }
    //cout<<cnt<<endl;
    return 0;
}/**/

Compilation message (stderr)

factories.cpp:136:2: warning: "/*" within comment [-Wcomment]
 }/**/
   
factories.cpp: In function 'int sizedfs(int, int)':
factories.cpp:3:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(a,b) for(int i=a;i<b;++i)
                               ~^~~~~~~~
 #define forj(a,b) for(int j=a;j<b;++j)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define fork(a,b) for(int k=a;k<b;++k)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 ~                               
 using namespace std;
 ~~~~~~~~~~~~~~~~~~~~~           
 const int N=500000;
 ~~~~~~~~~~~~~~~~~~~~            
 
 ~                               
 int par[N],sz[N],lvl[N],V,x,y,z,l,tot;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 long long ans[N],cd[N][19],xx,MAX=LLONG_MAX>>2;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 vector<int> gr[N],dist[N];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 bool blc[N];
 ~~~~~~~~~~~~~                   
 
 ~                               
 int sizedfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~       
 {
 ~~                              
     sz[v]=1;
     ~~~~~~~~~                   
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~         
factories.cpp:18:5: note: in expansion of macro 'fori'
     fori(0,gr[v].size())
     ^~~~
factories.cpp: In function 'int getCenter(int, int)':
factories.cpp:3:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(a,b) for(int i=a;i<b;++i)
                               ~^~~~~~~~
 #define forj(a,b) for(int j=a;j<b;++j)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define fork(a,b) for(int k=a;k<b;++k)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 ~                               
 using namespace std;
 ~~~~~~~~~~~~~~~~~~~~~           
 const int N=500000;
 ~~~~~~~~~~~~~~~~~~~~            
 
 ~                               
 int par[N],sz[N],lvl[N],V,x,y,z,l,tot;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 long long ans[N],cd[N][19],xx,MAX=LLONG_MAX>>2;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 vector<int> gr[N],dist[N];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 bool blc[N];
 ~~~~~~~~~~~~~                   
 
 ~                               
 int sizedfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~       
 {
 ~~                              
     sz[v]=1;
     ~~~~~~~~~                   
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~       
         if(!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             sz[v]+=sizedfs(gr[v][i],v);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     return sz[v];
     ~~~~~~~~~~~~~~              
 }
 ~~                              
 
 ~                               
 int getCenter(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 {
 ~~                              
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~         
factories.cpp:26:5: note: in expansion of macro 'fori'
     fori(0,gr[v].size())
     ^~~~
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:3:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(a,b) for(int i=a;i<b;++i)
                               ~^~~~~~~~
 #define forj(a,b) for(int j=a;j<b;++j)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define fork(a,b) for(int k=a;k<b;++k)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 ~                               
 using namespace std;
 ~~~~~~~~~~~~~~~~~~~~~           
 const int N=500000;
 ~~~~~~~~~~~~~~~~~~~~            
 
 ~                               
 int par[N],sz[N],lvl[N],V,x,y,z,l,tot;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 long long ans[N],cd[N][19],xx,MAX=LLONG_MAX>>2;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 vector<int> gr[N],dist[N];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 bool blc[N];
 ~~~~~~~~~~~~~                   
 
 ~                               
 int sizedfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~       
 {
 ~~                              
     sz[v]=1;
     ~~~~~~~~~                   
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~       
         if(!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             sz[v]+=sizedfs(gr[v][i],v);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     return sz[v];
     ~~~~~~~~~~~~~~              
 }
 ~~                              
 
 ~                               
 int getCenter(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 {
 ~~                              
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~       
         if(sz[gr[v][i]]>tot&&!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             return getCenter(gr[v][i],v);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     blc[v]=true;
     ~~~~~~~~~~~~~               
     return v;
     ~~~~~~~~~~                  
 }
 ~~                              
 
 ~                               
 void dfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~          
 {
 ~~                              
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~         
factories.cpp:35:5: note: in expansion of macro 'fori'
     fori(0,gr[v].size())
     ^~~~
factories.cpp: In function 'void build(int, int)':
factories.cpp:3:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(a,b) for(int i=a;i<b;++i)
                               ~^~~~~~~~
 #define forj(a,b) for(int j=a;j<b;++j)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define fork(a,b) for(int k=a;k<b;++k)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 ~                               
 using namespace std;
 ~~~~~~~~~~~~~~~~~~~~~           
 const int N=500000;
 ~~~~~~~~~~~~~~~~~~~~            
 
 ~                               
 int par[N],sz[N],lvl[N],V,x,y,z,l,tot;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 long long ans[N],cd[N][19],xx,MAX=LLONG_MAX>>2;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 vector<int> gr[N],dist[N];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 bool blc[N];
 ~~~~~~~~~~~~~                   
 
 ~                               
 int sizedfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~       
 {
 ~~                              
     sz[v]=1;
     ~~~~~~~~~                   
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~       
         if(!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             sz[v]+=sizedfs(gr[v][i],v);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     return sz[v];
     ~~~~~~~~~~~~~~              
 }
 ~~                              
 
 ~                               
 int getCenter(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 {
 ~~                              
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~       
         if(sz[gr[v][i]]>tot&&!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             return getCenter(gr[v][i],v);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     blc[v]=true;
     ~~~~~~~~~~~~~               
     return v;
     ~~~~~~~~~~                  
 }
 ~~                              
 
 ~                               
 void dfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~          
 {
 ~~                              
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~       
         if(!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         {
         ~~                      
             cd[gr[v][i]][l]=cd[v][l]+dist[v][i];
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             dfs(gr[v][i],v);
             ~~~~~~~~~~~~~~~~~   
         }
         ~~                      
 }
 ~~                              
 
 ~                               
 void build(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~        
 {
 ~~                              
     sizedfs(v,-1); tot=(sz[v]-1)>>1;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     v=getCenter(v,-1);
     ~~~~~~~~~~~~~~~~~~~         
     par[v]=p; lvl[v]=l; cd[v][l]=0;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     dfs(v,-1);
     ~~~~~~~~~~~                 
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~         
factories.cpp:49:5: note: in expansion of macro 'fori'
     fori(0,gr[v].size())
     ^~~~

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