Submission #339438

#	Time	Username	Problem	Language	Result	Execution time	Memory
339438		scales	Biochips (IZhO12_biochips)	C++17	100 / 100	1128 ms	25792 KiB

biochips

#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;
vector<int> graph[400001];
vector<int> viv;
int pred[400001],nov[400001],w=0,M=1000000007,f[400001],s[400001];
void dfs(int x, int p)
{
    int y=graph[x].size(),z,i;
    viv.push_back(x);
    f[x]=w;
    w++;
    for(i=0;i<y;i++)
    {
        z=graph[x][i];
        if(z!=p)
        {
            dfs(z,x);
        }
    }
    viv.push_back(x);
    s[x]=w;
    w++;
}
int main()
{
      ios::sync_with_stdio(false);
      cin.tie(0);
     // freopen("input.txt","r",stdin);
     // freopen("output.txt","w",stdout);
     int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
     cin>>n;
     cin>>m;
     vector<int> a(n);
     for(i=0;i<n;i++)
     {
         cin>>x;
         x--;
         if(x==-1)
         {
             start=i;
         }
         else
         {
             graph[i].push_back(x);
             graph[x].push_back(i);
         }
         cin>>a[i];
     }
     dfs(start,-1);
     x=viv.size();
     /*
     cout<<"x="<<x<<endl;
     for(i=0;i<x;i++)
     {
         cout<<viv[i]<<" ";
     }
     cout<<endl;
     for(i=0;i<n;i++)
     {
         cout<<"f["<<i<<"]="<<f[i]<<" s["<<i<<"]="<<s[i]<<endl;
     }*/
     for(i=0;i<=x;i++)
     {
        pred[i]=0;
     }
     for(j=1;j<=m;j++)
     {
         for(i=0;i<j;i++)
         {
             nov[i]=-M;
             //cout<<"nov["<<i<<"]="<<nov[i]<<endl;
         }
         for(i=j;i<=x;i++)
         {
             nov[i]=nov[i-1];
             if(s[viv[i-1]]==i-1)
             {
                 z=a[viv[i-1]];
                 y=f[viv[i-1]];
                 z=z+pred[y];
                 nov[i]=max(nov[i],z);
             }
             //cout<<"nov["<<i<<"]="<<nov[i]<<endl;
         }
         for(i=0;i<=x;i++)
         {
             pred[i]=nov[i];
         }
     }
     cout<<pred[x]<<endl;

    return 0;
}

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:36:11: warning: unused variable 't' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |           ^
biochips.cpp:36:17: warning: unused variable 'dno' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                 ^~~
biochips.cpp:36:21: warning: unused variable 'mini' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                     ^~~~
biochips.cpp:36:26: warning: unused variable 'sum' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                          ^~~
biochips.cpp:36:36: warning: unused variable 'q' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                                    ^
biochips.cpp:36:40: warning: unused variable 'l' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                                        ^
biochips.cpp:36:42: warning: unused variable 'r' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                                          ^
biochips.cpp:36:44: warning: unused variable 'k' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                                            ^
biochips.cpp:36:46: warning: unused variable 'v' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                                              ^
biochips.cpp:36:50: warning: unused variable 'kol' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                                                  ^~~
biochips.cpp:36:54: warning: unused variable 'g' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                                                      ^
biochips.cpp:36:56: warning: unused variable 'maxi' [-Wunused-variable]
   36 |      int  t,i,j,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,g,maxi,start;
      |                                                        ^~~~
biochips.cpp:55:9: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |      dfs(start,-1);
      |      ~~~^~~~~~~~~~

• Subtask 1: 100 / 100