Submission #340494

#	Time	Username	Problem	Language	Result	Execution time	Memory
340494		scales	Evacuation plan (IZhO18_plan)	C++17	0 / 100	688 ms	107108 KiB

plan

#include <bits/stdc++.h>
/*#ifndef LOCAL_RUN
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("fast-math")
    #pragma GCC target("avx2,tune=native")
#endif*/
using namespace std;
long long dist[100000],M=1000000007,c[100000],d[100000],g[100000],mini;
pair<long long,long long> pred[100000][31];
vector<pair<long long ,long long> > graph[100000],der[100000];
vector<long long> st(41);
struct reb
{
    long long x,y,z;
};
bool comp(reb a, reb b)
{
    return(a.z>b.z);
}
long long fun(long long x)
{
    if(c[x]==x)
    {
        return x;
    }
    else
    {
        c[x]=fun(c[x]);
        return c[x];
    }
}
void dfs(long long x,long long p)
{
    long long y=der[x].size(),i,z;
    for(i=0;i<y;i++)
    {
        z=der[x][i].second;
        if(z==p)
        {
            pred[x][0].first=der[x][i].first;
            pred[x][0].second=z;
        }
        else
        {
            g[z]=g[x]+1;
            dfs(z,x);
        }
    }
}
long long pod(long long x,long long p)
{
    if(p==0)
    {
        return x;
    }
    long long i,z;
    for(i=0;i<30;i++)
    {
        z=p&st[i];
        if(z!=0)
        {
            mini=min(mini,pred[x][i].first);
            x=pred[x][i].second;
            return pod(x,p-st[i]);
        }
    }
}
int main()
{
      ios::sync_with_stdio(false);
      cin.tie(0);
     // freopen("input.txt","r",stdin);
     // freopen("output.txt","w",stdout);
     long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
     st[0]=1;
     for(i=1;i<=31;i++)
     {
         st[i]=st[i-1]*2;
     }
     cin>>n;
     cin>>m;
     vector<reb> a(m);
     for(i=0;i<n;i++)
     {
         dist[i]=M;
         c[i]=i;
         d[i]=1;
     }
     for(i=0;i<m;i++)
     {
         cin>>x;
         cin>>y;
         cin>>z;
         x--;
         y--;
         graph[x].push_back({y,z});
         graph[y].push_back({x,z});
         a[i].x=x;
         a[i].y=y;
     }
     priority_queue <pair<long long, long long> > q;
     cin>>k;
     for(i=0;i<k;i++)
     {
         cin>>x;
         x--;
         dist[x]=0;
         q.push({0,x});
     }
     while(!q.empty())
     {
         x=q.top().first;
         y=q.top().second;
         q.pop();
         x=-x;
         if(dist[y]>=x)
         {
             x=y;
             y=graph[x].size();
             for(i=0;i<y;i++)
             {
                 z=graph[x][i].first;
                 w=graph[x][i].second+dist[x];
                 if(dist[z]>w)
                 {
                     q.push({-w,z});
                     dist[z]=w;
                 }
             }
         }
     }
     for(i=0;i<m;i++)
     {
         x=a[i].x;
         y=a[i].y;
         z=min(dist[x],dist[y]);
         a[i].z=z;
     }
     sort(a.begin(),a.end(),comp);
     /*for(i=0;i<n;i++)
     {
         cout<<"dist["<<i<<"]="<<dist[i]<<endl;
     }*/
     k=0;
     i=0;
     while(k!=n-1)
     {
         x=a[i].x;
         y=a[i].y;
         //cout<<"x="<<x<<" y="<<y<<" ";
         x1=x;
         y1=y;
         x=fun(x);
         y=fun(y);
         //cout<<"x="<<x<<" y="<<y<<endl;
         if(x!=y)
         {
             //cout<<"aaaaaaaaaa"<<" x1="<<x1<<" y1="<<y1<<endl;
             if(d[x]>=d[y])
             {
                 c[y]=x;
                 d[x]=d[x]+d[y];
             }
             else
             {
                 c[x]=y;
                 d[y]=d[y]+d[x];
             }
             k++;
             der[x1].push_back({min(dist[x1],dist[y1]),y1});
             der[y1].push_back({min(dist[x1],dist[y1]),x1});
         }
         i++;
     }
     for(i=0;i<n;i++)
     {
         x=fun(i);
     }


     pred[0][0].first=M*M;
     pred[0][0].second=0;
     g[0]=0;
     dfs(0,-1);
     /*for(i=0;i<n;i++)
     {
         cout<<"i="<<i<<" "<<pred[i][0].first<<" "<<pred[i][0].second<<endl;
     }*/
     //return 0;
     for(j=1;j<=30;j++)
     {
         //cout<<"j="<<j<<endl;
         for(i=0;i<n;i++)
         {
             y=pred[i][j-1].second;
             //cout<<"bbbbbbbb"<<endl;
             x=min(pred[y][j-1].first,pred[i][j-1].first);
             //cout<<"cccccccc"<<endl;
             y=pred[y][j-1].second;
             //cout<<"aaaaaa"<<endl;
             pred[i][j]={x,y};
         }
     }
     cin>>t;
     for(w=0;w<t;w++)
     {
         mini=M;
         cin>>x;
         cin>>y;
         x--;
         y--;
         if(g[x]>g[y])
         {
             swap(x,y);
         }
         r=g[y]-g[x];
         y=pod(y,r);
         //cout<<"y="<<y<<endl;
         i=30;
         while(i!=-1)
         {
            f=pred[x][i].second;
            s=pred[y][i].second;
            if(s==f)
            {

            }
            else
            {
                mini=min({mini,pred[x][i].first,pred[y][i].first});
                x=f;
                y=s;
            }
            i--;
         }
         x=pod(x,1);
         y=pod(y,1);
         cout<<mini<<endl;
     }


    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:75:22: warning: unused variable 'dno' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                      ^~~
plan.cpp:75:46: warning: unused variable 'tip' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                              ^~~
plan.cpp:75:50: warning: unused variable 'p' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                  ^
plan.cpp:75:52: warning: unused variable 'l' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                    ^
plan.cpp:75:56: warning: unused variable 'sum' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                        ^~~
plan.cpp:75:60: warning: unused variable 'maxi' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                            ^~~~
plan.cpp:75:65: warning: unused variable 'kol' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                                 ^~~
plan.cpp:75:69: warning: unused variable 'v' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                                     ^
plan.cpp:75:75: warning: unused variable 'h' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                                           ^
plan.cpp:75:77: warning: unused variable 'z1' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                                             ^~
plan.cpp:75:80: warning: unused variable 'rov' [-Wunused-variable]
   75 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                                                ^~~
plan.cpp: In function 'long long int pod(long long int, long long int)':
plan.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46