Submission #1283698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283698		Faisal_Saqib	Easter Eggs (info1cup17_eastereggs)	C++20	Compilation error	0 ms	0 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<64> 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)] or (pos[(sz/2)+1] and sz%2==1))
            {
                // cout<<"Copmuting dp"<<endl;
                vector<int> dp(64,-1);    
                dp[1]=y;
                for(auto oe:ma[y])
                {
                    if(oe==par[y])continue;
                    for(int q=63-sub[oe];q>=0;q--)
                    {
                        if(dp[q]!=-1)
                        {
                            dp[q+sub[oe]]=oe;
                        }
                    }
                }
                 if(par[y]!=-1)
                {
                    for(int q=63-(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(cur.size()==0)
        // {
        //     exit(-1);
        // }
        // assert(cur.size()>0);
        if(cur.size()==0)
        {
            cur.push_back(x);
        }
        if(query(cur))
        {
            rem.clear();
            for(auto x:cur)rem.insert(x);
        }
        else
        {
            for(auto x:cur)rem.erase(x);
        }
        cur.clear();
    }
    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;
// }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccfWULnJ.o: in function `query(std::vector<int, std::allocator<int> >)':
grader.cpp:(.text+0x0): multiple definition of `query(std::vector<int, std::allocator<int> >)'; /tmp/ccQTfc9R.o:eastereggs.cpp:(.text+0x2b0): first defined here
/usr/bin/ld: /tmp/ccfWULnJ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQTfc9R.o:eastereggs.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status