제출 #1283744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283744		Faisal_Saqib	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	1076 ms	564 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);
        // cout<<"X: "<<x<<" SZ done"<<endl;
        for(auto x:rem)
        {
            dfs_(x);
            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;
                int asy=pos._Find_next((sz/2)-1);
                if(asy>=sz)continue;
                // if(pos[(sz/2)] or (pos[(sz/2)+1] and sz%2==1))
                // cout<<"asy: "<<asy<<' '<<pos[asy]<<endl;
                {
                    // 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=asy;
                    set<int> want; // 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)
            {
                continue;
                // return 0;// Wrong Answer
                // cur.push_back(x);
            }
            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();
            break;
        }
    }
    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: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20