Submission #111526

#	Time	Username	Problem	Language	Result	Execution time	Memory
111526		discoverMeMe	Factories (JOI14_factories)	C++14	15 / 100	8100 ms	179592 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 lvl[N],par[N],sz[N],V,x,y,z,tot,l,cnt;
long long ans[N],cd[N][19],xx;
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)
{
    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);
    blc[v]=true;
    return v;
}

void dfs(int v,int p)
{
    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);
        }
}

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); tot=sz[x];
        y=getCenter(x,-1);
        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>>2;
        cd[i][lvl[i]]=0; l=lvl[i];
        if(l>=19)
            cout<<1/0;
        dfs(i,-1);
    }
}
long long Query(int s,int a[],int t,int b[])
{
    xx=LLONG_MAX>>2;
    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>>2)
        {
            ans[x]=LLONG_MAX>>2;
            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-01.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:146:2: warning: "/*" within comment [-Wcomment]
 }/**/
   
factories.cpp: In function 'void 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 lvl[N],par[N],sz[N],V,x,y,z,tot,l,cnt;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 long long ans[N],cd[N][19],xx;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 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)':
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 lvl[N],par[N],sz[N],V,x,y,z,tot,l,cnt;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 long long ans[N],cd[N][19],xx;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 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)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 {
 ~~                              
     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)':
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 lvl[N],par[N],sz[N],V,x,y,z,tot,l,cnt;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 long long ans[N],cd[N][19],xx;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 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)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 {
 ~~                              
     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);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     blc[v]=true;
     ~~~~~~~~~~~~~               
     return v;
     ~~~~~~~~~~                  
 }
 ~~                              
 
 ~                               
 void dfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~          
 {
 ~~                              
     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: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 lvl[N],par[N],sz[N],V,x,y,z,tot,l,cnt;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 long long ans[N],cd[N][19],xx;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 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)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 {
 ~~                              
     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);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     blc[v]=true;
     ~~~~~~~~~~~~~               
     return v;
     ~~~~~~~~~~                  
 }
 ~~                              
 
 ~                               
 void dfs(int v,int p)
 ~~~~~~~~~~~~~~~~~~~~~~          
 {
 ~~                              
     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);
             ~~~~~~~~~~~~~~~~~   
         }
         ~~                      
 }
 ~~                              
 
 ~                               
 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); tot=sz[x];
         ~~~~~~~~~~~~~~~~~~~~~~~~~~
         y=getCenter(x,-1);
         ~~~~~~~~~~~~~~~~~~~     
         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())
         ^~~~
factories.cpp:82:20: warning: division by zero [-Wdiv-by-zero]
             cout<<1/0;
                   ~^~

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