Submission #1283692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283692		Faisal_Saqib	Easter Eggs (info1cup17_eastereggs)	C++20	6 / 100	2 ms	428 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
// // #include "grader.cpp"

using namespace std;
const int TP=513;
// vector<int> ma[TP];
int n,sub[TP],deg[TP],par[TP];
// set<int> rem;
// int sz,fv=-1;
// vector<int> cur;
// void compute(int x,int p)
// {
//     // cout<<"AT "<<x<<' '<<p<<endl;
//     for(auto y:ma[x])
//     {
//         if(y==p)continue;
//         compute(y,x);
//     }
//     cur.push_back(x);
// }
// void dfs_(int x,int p=-1)
// {
//     sub[x]=1;
//     par[x]=p;
//     for(auto y:ma[x])
//     {
//         if(y==p)continue;
//         dfs_(y,x);
//         sub[x]+=sub[y];
//     }
//     // if(sub[x]==(sz/2))
//     // {
//     //     fv=x;
//     // }
// }
// int find_centriod(int x,int p=-1)
// {
//     for(auto y:ma[x])
//     {
//         if(y!=p and sub[y]>(sz/2))
//         {
//             sub[x]-=sub[y];
//             sub[y]+=sub[x];
//             return find_centriod(y,x);
//         }
//     }
//     return x;
// }
// int findEgg (int N, vector < pair < int, int > > edge)
// {
//     n=N;
//     for(int i=0;i<=n;i++)ma[i].clear();
//     for(int i=0;i<n-1;i++)
//     {
//         ma[edge[i].first].push_back(edge[i].second);
//         ma[edge[i].second].push_back(edge[i].first);
//     }
//     rem.clear();
//     for(int i=1;i<=n;i++)
//     {
//         rem.insert(i);
//     }
//     while(rem.size()>1) // 9 time 
//     {
//         sz=rem.size();
//         // cout<<"Cur "<<sz<<endl;
//         int x=*begin(rem);
//         dfs_(x);
//         // cout<<"X: "<<x<<" SZ done"<<endl;
//         for(auto y:rem)
//         {
//             bitset<520> pos;
//             pos[1]=1; // only y
//             for(auto oe:ma[y])
//             {
//                 if(oe==par[y])continue;
//                 pos|=(pos<<sub[oe]); // y along some other subtree
//             }
//             if(par[y]!=-1)
//             {
//                 pos|=(pos<<(sz-sub[y])); // y along with other subtree
//             }
//             // 2x we need to find connected x node
//             // 2x+1  x x+1
//             // cout<<"Compute bitset "<<y<<endl;
//             if(pos[(sz/2)])
//             {
//                 // cout<<"Copmuting dp"<<endl;
//                 vector<int> dp(530,-1);    
//                 dp[1]=y;
//                 for(auto oe:ma[y])
//                 {
//                     if(oe==par[y])continue;
//                     for(int q=519-sub[oe];q>=0;q--)
//                     {
//                         if(dp[q]!=-1)
//                         {
//                             dp[q+sub[oe]]=oe;
//                         }
//                     }
//                 }
//                  if(par[y]!=-1)
//                 {
//                     for(int q=519-(sz-sub[y]);q>=0;q--)
//                     {
//                         if(dp[q]!=-1)
//                         {
//                             dp[q+(sz-sub[y])]=par[y];
//                         }
//                     }
//                 }
//                 // cout<<"Dp done"<<endl;
//                 int zy=sz/2;
//                 set<int> want={y}; // we surely take y
//                 while(zy>0)
//                 {
//                     // cout<<"Vertex "<<dp[zy]<<" added to answer"<<endl;
//                     want.insert(dp[zy]);
//                     int yp=dp[zy];
//                     if(yp==y)
//                     {
//                         // cout<<"SELF "<<1<<endl;
//                         zy-=1;
//                     }
//                     else if(yp==par[y])
//                     {
//                         // cout<<"Sizep "<<sz-sub[y]<<endl;
//                         zy-=(sz-sub[y]);
//                     }
//                     else
//                     {
//                         // cout<<"Sizec "<<sub[yp]<<endl;
//                         zy-=sub[yp];
//                     }
//                 }
//                 cur.clear();
//                 cur.push_back(y);
//                 // cout<<"Subtree "<<endl;
//                 for(auto yp:ma[y])
//                 {
//                     if(want.find(yp)!=want.end())
//                     {
//                         compute(yp,y);
//                     }
//                 }
//                 // cout<<"Final done"<<endl;
//                 break;
//             }
//         }
//         // cout<<"Found cur: ";
//         // for(auto x:cur)cout<<x<<' ';
//         // cout<<endl;
//         if(query(cur))
//         {
//             rem.clear();
//             for(auto x:cur)rem.insert(x);
//         }
//         else
//         {
//             for(auto x:cur)rem.erase(x);
//         }
//     }
//     return *begin(rem);
// }
int findEgg (int N, vector < pair < int, int > > edge)
{
    n=N;
    for(int i=0;i<n-1;i++)
    {
        deg[edge[i].first]++;
        deg[edge[i].second]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(query({i}))return i;
    }
    return 0;
}

• Subtask 1: 6 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20