제출 #1283792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283792		Faisal_Saqib	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	2 ms	580 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);
            pair<int,int> mi={1e9,1e9};
            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);
                mi=min(mi,{asy,y});
            }
            int asy=mi.first;
            int y=mi.second;
            // cout<<"Copmuting dp"<<endl;
            // cout<<"Min "<<asy<<' '<<y<<endl;
            vector<vector<int>> dp(530);    
            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].size()>0)
                    {
                        dp[q+sub[oe]]=dp[q];
                        dp[q+sub[oe]].push_back(oe);
                    }
                }
            }
            if(par[y]!=-1)
            {
                for(int q=519-(sz-sub[y]);q>=0;q--)
                {
                    if(dp[q].size()>0)
                    {
                        dp[q+(sz-sub[y])]=dp[q];
                        dp[q+(sz-sub[y])].push_back(par[y]);
                    }
                }
            }
            // cout<<"Dp done"<<endl;
            int zy=asy;
            set<int> want(begin(dp[zy]),end(dp[zy])); // 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);
            cur.push_back(x);
            // cout<<"WANT: ";
            // for(auto tp:want)cout<<tp<<' ';
            // cout<<endl;
            // cout<<"Subtree "<<endl;
            for(auto yp:ma[y])
            {
                if(want.find(yp)!=want.end())
                {
                    compute(yp,y);
                }
            }
            // cout<<"CUR: ";
            // for(auto i:cur)cout<<i<<' ';
            // 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();
            // 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