Submission #1283753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283753		Faisal_Saqib	Easter Eggs (info1cup17_eastereggs)	C++17	10 / 100	663 ms	548 KiB

eastereggs

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

using namespace std;
const int TP=533;
set<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].insert(edge[i].second);
        ma[edge[i].second].insert(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);
        vector<int> best={1000000000,-1,-1};
        // dfs_(x);
        for(auto i:rem)
        {
            dfs_(i);
            // for(int j=1;j<=n;j++)
            for(auto j:rem)
            {
                best=min(best,{max(sz-sub[j],sub[j]),j,i});
            }
        }
        // cout<<best[0]<<' '<<best[1]<<' '<<best[2]<<endl;
        dfs_(best[2]);
        cur.clear();
        compute(best[1],par[best[1]]);
        // cout<<"CUR: ";
        // for(auto x:cur)cout<<x<<' ';
        // cout<<endl;
        if(query(cur))
        {
            sort(begin(cur),end(cur));
            for(auto xa:rem)
            {
                auto it=lower_bound(begin(cur),end(cur),xa);
                if(it==end(cur) or *it!=xa)
                {
                    for(auto y:ma[xa])
                    {
                        ma[y].erase(xa);
                    }
                    ma[xa].clear();
                    // we will delete this
                    // int x=y;
                }
            }
            rem.clear();
            for(auto x:cur)rem.insert(x);
        }
        else
        {
            for(auto xa:cur)
            {
                for(auto y:ma[xa])
                {
                    ma[y].erase(xa);
                }
                ma[xa].clear();
                rem.erase(xa);
            }
        }
        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;
// }

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