Submission #682101

#	Time	Username	Problem	Language	Result	Execution time	Memory
682101		auslander	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	49 ms	51516 KiB

eastereggs

#include <vector>
#include <set>
#include "grader.h"

using namespace std;

vector<int>g[515];
vector<int>sons[515];
bool color[515];
void fsons(int a)
{
    color[a] = true;
    for (int i = 0; i < g[a].size(); i++)
    {
        if (!color[g[a][i]])
        {
            fsons(g[a][i]);
            for (int j = 0; j < sons[g[a][i]].size(); j++)
            {
                sons[a].push_back(sons[g[a][i]][j]);
            }
            sons[a].push_back(g[a][i]);
        }
    }
}
int ask(vector<int>h, bool w, int k)
{
    int i, j;
    vector<int>v;
    if (h.size() == 1)
    {
        int a = h[0];
        if (g[a].size() == 2)
        {
            h.push_back(sons[a][sons[a].size() - 1]);
            return ask(h, 1, sons[a][sons[a].size() - 1]);
        }
        else if (g[a].size() == 1)
        {
            return a;
        }
        else
        {
            if (!query(sons[a]))
                return a;

            for (i = sons[a].size() - 1, j = 0; j < g[a].size() - 1; j++, i--)
            {
                if (query(sons[sons[a][i]]))
                {
                    v.push_back(sons[a][i]);
                    return ask(v, 1, 0);
                }
            }
            v.push_back(sons[a][i]);

            return ask(v, 1, 0);
        }
    }
    else
    {
        int a = h[h.size() - 1];
        if (g[a].size() == 2 && w)
        {
            h.push_back(sons[a][sons[a].size() - 1]);
            return ask(h, 1, sons[a][sons[a].size() - 1]);
        }
        else
        {
            vector<int>v1, v2;
            for (i = 0; i < h.size() / 2; i++)
            {
                v1.push_back(h[i]);
            }
            for (i = h.size() / 2; i < h.size(); i++)
            {
                v2.push_back(h[i]);
            }
            if (query(v1))
            {
                if (v1.size() != 1)
                    ask(v1, 0, k);
                else return v1[0];
            }
            else if (query(v2))
            {
                if (v2.size() != 1)
                    ask(v2, 0, k);
                else return v2[0];
            }
            else
            {
                v.push_back(k);
                return ask(v, 1, k);
            }
        }
    }
}
int findEgg(int N, vector < pair < int, int > > bridges)
{
    int n = N;
    if (n == 1)
    {
        return 1;
    }
    int i, j;
    for (i = 0; i < bridges.size(); i++)
    {
        g[bridges[i].first].push_back(bridges[i].second);
        g[bridges[i].second].push_back(bridges[i].first);
    }
    fsons(1);
    for (i = 0; i < n; i++)
        color[i] = 0;
    vector<int>v;
    v.push_back(1);
    return ask(v, 1, 0);
}

Compilation message (stderr)

eastereggs.cpp: In function 'void fsons(int)':
eastereggs.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < g[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~
eastereggs.cpp:18:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |             for (int j = 0; j < sons[g[a][i]].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int ask(std::vector<int>, bool, int)':
eastereggs.cpp:47:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for (i = sons[a].size() - 1, j = 0; j < g[a].size() - 1; j++, i--)
      |                                                 ~~^~~~~~~~~~~~~~~~~
eastereggs.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for (i = 0; i < h.size() / 2; i++)
      |                         ~~^~~~~~~~~~~~~~
eastereggs.cpp:75:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for (i = h.size() / 2; i < h.size(); i++)
      |                                    ~~^~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:107:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (i = 0; i < bridges.size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~
eastereggs.cpp:106:12: warning: unused variable 'j' [-Wunused-variable]
  106 |     int i, j;
      |            ^
eastereggs.cpp: In function 'int ask(std::vector<int>, bool, int)':
eastereggs.cpp:29:16: warning: control reaches end of non-void function [-Wreturn-type]
   29 |     vector<int>v;
      |                ^

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