Submission #649429

#	Time	Username	Problem	Language	Result	Execution time	Memory
649429		berr	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	10 ms	1248 KiB

eastereggs

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

using namespace std;
vector<int> adj[513], de(513), val(513), zort[513];
int n, all, ans=-1;

void dfs(int v, int p)
{
    val[v]=0;

    if(de[v]==0) 
    {
        for(auto i: adj[v])
        {
            if(i==p||de[i]) continue;
            dfs(i, v);
            val[v]+=val[i];
        }

        val[v]++;
    }
}

void dfs2(int v, int p)
{

    zort[v].clear();

    zort[v].push_back(v);


    if(de[v]==0)
    {
        for(auto i: adj[v])
        {
            if(i==p||de[i]) continue;
            dfs2(i, v);
            if(p!=v)
            {
                for(auto l: zort[i]) zort[v].push_back(l);
            }
        }

    }
}


array<int, 2> decide(int v)
{
    val[v]=-1;
    dfs(v, v);

    vector<int> q;

    for(int i=0; i<=n; i++) zort[i].clear();
    for(auto i: adj[v])
    {
        if(de[i]) continue;

        q.push_back(val[i]);
    }

    sort(q.begin(), q.end());
    reverse(q.begin(), q.end());

    array<int, 2> h={1, 1};

    for(auto i: q)
    {

        if(abs((h[0]+i)-h[1])<=abs((h[0])-(h[1]+i)))
        {
            h[0]+=i;
        }
        else
        {
            h[1]+=i;
        }
    }

    array<int, 2> p={0, 1};

    p[0]=q[0];

    for(int i=1; i<q.size(); i++)
    {
        p[1]+=i;
    }

    if(abs(p[0]-p[1])<=abs(h[0]-h[1])) h=p;

    return h;

}
void findroot()
{

    array<int, 2> q{(int)1e9, 0};
    int ind =0;
    for(int i=1; i<=n; i++)
    {

        if(de[i]==0)
        {
            auto p=decide(i);

            if((abs(p[1]-p[0])<=abs(q[1]-q[0]))||((abs(p[1]-p[0])==abs(q[1]-q[0]))&&q[1]+q[0]>p[1]+p[0]))
            {
                ind = i;
                q=p;
            }
        }
    }

    dfs2(ind, ind);

    vector<array<int, 2>> qq;

    for(auto i: adj[ind])
    {
        if(de[i]) continue;
        qq.push_back({(int)zort[i].size(), i});
    }

    sort(qq.begin(), qq.end());
    reverse(qq.begin(), qq.end());

    vector<int> h0, h1;

    array<int,2> a={1, 1};

    h1.push_back(ind);
    h0.push_back(ind);



    for(auto i: qq)
    {
        if(abs((a[0]+i[0])-a[1])<abs(a[0]-(a[1]+i[0])))
        {
            for(auto l: zort[i[1]])
            {
                h0.push_back(l);
            }   
            a[0]+=i[0];

        }
        else
        {
            for(auto l: zort[i[1]])
            {
                h1.push_back(l);
            }   
            a[1]+=i[0];
        }
    }

    if(abs((a[1]+a[0]-1)-qq[0][0])<=abs(a[0]-a[1]))
    {
        h0.clear();
        h1.clear();

        for(auto i: zort[qq[0][1]])
        {
            h0.push_back(i);
        }

        h1.push_back(ind);

        for(int i=1; i<qq.size(); i++)
        {
            for(auto l: zort[qq[i][1]])
            {
                h0.push_back(l);
            }
        }
    }

    if(all==2)
    {
        vector<int> f;
        for(int i=1; i<=n; i++)
        {
            if(de[i]==0) f.push_back(i);
        }
        h1.clear();
        h0.clear();
        h1.push_back(f[0]);
        h0.push_back(f[1]);
    }



    for(int i=0; i<=n; i++) de[i]=1;
        all=0;

        int p=query(h0); 
    if(p)
    {
        for(auto i: h0)
        {
            all++;
            de[i]=0;
        }
    }
    else
    {
        for(auto i: h1)
        {
            all++;
            de[i]=0;
        }
    }


}


int findEgg(int N, vector < pair < int, int > > bridges)
{

    all=n=N;

    for(auto i: bridges)
    {
        adj[i.first].push_back(i.second);

        adj[i.second].push_back(i.first);
    }

    int pf=100;
    while(all>1&&pf--)
    {
        findroot();


    }

    for(int i=1; i<=N&&ans; i++)
    {
        if(de[i]==0) ans=i;
    }

    return ans;
}

Compilation message (stderr)

eastereggs.cpp: In function 'std::array<int, 2> decide(int)':
eastereggs.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=1; i<q.size(); i++)
      |                  ~^~~~~~~~~
eastereggs.cpp: In function 'void findroot()':
eastereggs.cpp:171:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |         for(int i=1; i<qq.size(); i++)
      |                      ~^~~~~~~~~~

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