Submission #111390

#	Time	Username	Problem	Language	Result	Execution time	Memory
111390		discoverMeMe	Factories (JOI14_factories)	C++14	15 / 100	8010 ms	179144 KiB

factories

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

using namespace std;
const int N=500000;

int lvl[N],par[N],sz[N],V,x,y,z,cnt;
long long ans[N],cd[N][19];
vector<int> gr[N],dist[N];
bool blc[N];
queue<int> sub;

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

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

void dfs(int v,int p,int l)
{
    fori(0,gr[v].size())
        if(lvl[gr[v][i]]>l&&gr[v][i]!=p)
        {
            cd[gr[v][i]][l]=cd[v][l]+dist[v][i];
            dfs(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]=LLONG_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]);
    }
    sub.push(0); par[0]=-1;
    while(!sub.empty())
    {
        x=sub.front(); sub.pop();
        sizedfs(x,-1);
        y=getCenter(x,-1,sz[x]);
        par[y]=par[x];
        if(par[y]!=-1)
            lvl[y]=lvl[par[y]]+1;
        fori(0,gr[y].size())
        {
            if(!blc[gr[y][i]])
            {
                sub.push(gr[y][i]);
                par[gr[y][i]]=y;
            }
        }
    }
    fori(0,V)
    {
        ans[i]=LLONG_MAX/4;
        cd[i][lvl[i]]=0;
        dfs(i,-1,lvl[i]);
    }
}
long long Query(int s,int a[],int t,int b[])
{
    long long xx=LLONG_MAX/4;
    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,0LL+ans[x]+cd[a[i]][lvl[x]]);
            x=par[x];
        }
    }
    fori(0,t)
    {
        x=b[i];
        while(x!=-1&&ans[x]!=LLONG_MAX/4)
        {
            ans[x]=LLONG_MAX/4;
            x=par[x];
        }
    }
    return xx;
}
/*
int a[N],b[N],c[N],xx[N],yy[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>>xx[i];
        fori(0,y)
            cin>>yy[i];
        cout<<Query(x,xx,y,yy)<<"\n";
    }
    cout<<cnt<<endl;
    return 0;
}/**/

Compilation message (stderr)

factories.cpp:144:2: warning: "/*" within comment [-Wcomment]
 }/**/
   
factories.cpp: In function 'void sizedfs(int, int)':
factories.cpp:3:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(a,b) for(long long i=a;i<b;i++)
                                     ~^~~~~~~~
 #define forj(a,b) for(long long j=a;j<b;j++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define fork(a,b) for(long long k=a;k<b;k++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 ~                                     
 using namespace std;
 ~~~~~~~~~~~~~~~~~~~~~                 
 const int N=500000;
 ~~~~~~~~~~~~~~~~~~~~                  
 
 ~                                     
 int lvl[N],par[N],sz[N],V,x,y,z,cnt;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 long long ans[N],cd[N][19];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
 vector<int> gr[N],dist[N];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~           
 bool blc[N];
 ~~~~~~~~~~~~~                         
 queue<int> sub;
 ~~~~~~~~~~~~~~~~                      
 
 ~                                     
 void sizedfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~            
 {
 ~~                                    
     sz[v]=1;
     ~~~~~~~~~                         
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~               
factories.cpp:19:5: note: in expansion of macro 'fori'
     fori(0,gr[v].size())
     ^~~~
factories.cpp: In function 'int getCenter(int, int, int)':
factories.cpp:3:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(a,b) for(long long i=a;i<b;i++)
                                     ~^~~~~~~~
 #define forj(a,b) for(long long j=a;j<b;j++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define fork(a,b) for(long long k=a;k<b;k++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 ~                                     
 using namespace std;
 ~~~~~~~~~~~~~~~~~~~~~                 
 const int N=500000;
 ~~~~~~~~~~~~~~~~~~~~                  
 
 ~                                     
 int lvl[N],par[N],sz[N],V,x,y,z,cnt;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 long long ans[N],cd[N][19];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
 vector<int> gr[N],dist[N];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~           
 bool blc[N];
 ~~~~~~~~~~~~~                         
 queue<int> sub;
 ~~~~~~~~~~~~~~~~                      
 
 ~                                     
 void sizedfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~            
 {
 ~~                                    
     sz[v]=1;
     ~~~~~~~~~                         
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~             
     {
     ~~                                
         if(!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         {
         ~~                            
             sizedfs(gr[v][i],v);
             ~~~~~~~~~~~~~~~~~~~~~     
             sz[v]+=sz[gr[v][i]];
             ~~~~~~~~~~~~~~~~~~~~~     
         }
         ~~                            
     }
     ~~                                
 }
 ~~                                    
 
 ~                                     
 int getCenter(int v,int p,int tot)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~   
 {
 ~~                                    
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~               
factories.cpp:31:5: note: in expansion of macro 'fori'
     fori(0,gr[v].size())
     ^~~~
factories.cpp: In function 'void dfs(int, int, int)':
factories.cpp:3:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(a,b) for(long long i=a;i<b;i++)
                                     ~^~~~~~~~
 #define forj(a,b) for(long long j=a;j<b;j++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define fork(a,b) for(long long k=a;k<b;k++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 ~                                     
 using namespace std;
 ~~~~~~~~~~~~~~~~~~~~~                 
 const int N=500000;
 ~~~~~~~~~~~~~~~~~~~~                  
 
 ~                                     
 int lvl[N],par[N],sz[N],V,x,y,z,cnt;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 long long ans[N],cd[N][19];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
 vector<int> gr[N],dist[N];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~           
 bool blc[N];
 ~~~~~~~~~~~~~                         
 queue<int> sub;
 ~~~~~~~~~~~~~~~~                      
 
 ~                                     
 void sizedfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~            
 {
 ~~                                    
     sz[v]=1;
     ~~~~~~~~~                         
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~             
     {
     ~~                                
         if(!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         {
         ~~                            
             sizedfs(gr[v][i],v);
             ~~~~~~~~~~~~~~~~~~~~~     
             sz[v]+=sz[gr[v][i]];
             ~~~~~~~~~~~~~~~~~~~~~     
         }
         ~~                            
     }
     ~~                                
 }
 ~~                                    
 
 ~                                     
 int getCenter(int v,int p,int tot)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~   
 {
 ~~                                    
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~             
         if(sz[gr[v][i]]*2>tot&&!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             return getCenter(gr[v][i],v,tot);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     blc[v]=true;
     ~~~~~~~~~~~~~                     
     return v;
     ~~~~~~~~~~                        
 }
 ~~                                    
 
 ~                                     
 void dfs(int v,int p,int l)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
 {
 ~~                                    
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~               
factories.cpp:40:5: note: in expansion of macro 'fori'
     fori(0,gr[v].size())
     ^~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:3:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(a,b) for(long long i=a;i<b;i++)
                                     ~^~~~~~~~
 #define forj(a,b) for(long long j=a;j<b;j++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define fork(a,b) for(long long k=a;k<b;k++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 ~                                     
 using namespace std;
 ~~~~~~~~~~~~~~~~~~~~~                 
 const int N=500000;
 ~~~~~~~~~~~~~~~~~~~~                  
 
 ~                                     
 int lvl[N],par[N],sz[N],V,x,y,z,cnt;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 long long ans[N],cd[N][19];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
 vector<int> gr[N],dist[N];
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~           
 bool blc[N];
 ~~~~~~~~~~~~~                         
 queue<int> sub;
 ~~~~~~~~~~~~~~~~                      
 
 ~                                     
 void sizedfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~            
 {
 ~~                                    
     sz[v]=1;
     ~~~~~~~~~                         
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~             
     {
     ~~                                
         if(!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         {
         ~~                            
             sizedfs(gr[v][i],v);
             ~~~~~~~~~~~~~~~~~~~~~     
             sz[v]+=sz[gr[v][i]];
             ~~~~~~~~~~~~~~~~~~~~~     
         }
         ~~                            
     }
     ~~                                
 }
 ~~                                    
 
 ~                                     
 int getCenter(int v,int p,int tot)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~   
 {
 ~~                                    
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~             
         if(sz[gr[v][i]]*2>tot&&!blc[gr[v][i]]&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             return getCenter(gr[v][i],v,tot);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     blc[v]=true;
     ~~~~~~~~~~~~~                     
     return v;
     ~~~~~~~~~~                        
 }
 ~~                                    
 
 ~                                     
 void dfs(int v,int p,int l)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
 {
 ~~                                    
     fori(0,gr[v].size())
     ~~~~~~~~~~~~~~~~~~~~~             
         if(lvl[gr[v][i]]>l&&gr[v][i]!=p)
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         {
         ~~                            
             cd[gr[v][i]][l]=cd[v][l]+dist[v][i];
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             dfs(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]=LLONG_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]);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     }
     ~~                                
     sub.push(0); par[0]=-1;
     ~~~~~~~~~~~~~~~~~~~~~~~~          
     while(!sub.empty())
     ~~~~~~~~~~~~~~~~~~~~              
     {
     ~~                                
         x=sub.front(); sub.pop();
         ~~~~~~~~~~~~~~~~~~~~~~~~~~    
         sizedfs(x,-1);
         ~~~~~~~~~~~~~~~               
         y=getCenter(x,-1,sz[x]);
         ~~~~~~~~~~~~~~~~~~~~~~~~~     
         par[y]=par[x];
         ~~~~~~~~~~~~~~~               
         if(par[y]!=-1)
         ~~~~~~~~~~~~~~~               
             lvl[y]=lvl[par[y]]+1;
             ~~~~~~~~~~~~~~~~~~~~~~    
         fori(0,gr[y].size())
         ~~~~~~~~~~~~~~~~~~~           
factories.cpp:68:9: note: in expansion of macro 'fori'
         fori(0,gr[y].size())
         ^~~~

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