Submission #1280924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280924		SSKMF	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	10 ms	484 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;

int findEgg (int numar_noduri , vector < pair <int, int> > muchii)
{
    vector <int> adiacenta[513];
    int moment[513] = { } , masca[513] = { };
    for (auto& muchie : muchii)
    {
        adiacenta[muchie.first].push_back(muchie.second);
        adiacenta[muchie.second].push_back(muchie.first);
    }

    int ramas = numar_noduri , __masca = 0;
    while (ramas > 1)
    {
        moment[0]++;
        queue <int> candidati;
        vector <int> gasit , total;
        for (candidati.push(1) , moment[1] = moment[0] ; true ; candidati.pop())
        {
            int& nod = candidati.front();
            if ((masca[nod] & __masca) == __masca)
            {
                total.push_back(nod);
                if (masca[nod] == __masca)
                    { gasit.push_back(nod); }

                if ((int)gasit.size() == ramas / 2)
                    { break; }
                
                for (auto& vecin : adiacenta[nod]) {
                    if (moment[vecin] != moment[0])
                    {
                        moment[vecin] = moment[0];
                        candidati.push(vecin);
                    }
                }
            }
        }

        const int putere = (1 << (moment[0] - 1));
        for (auto& nod : total)
            { masca[nod] |= putere; }

        if (query(total))
            { __masca |= putere; ramas = (int)gasit.size(); }
        else
            { ramas -= (int)gasit.size(); }
    }

    int nod = 1;
    while (masca[nod] != __masca)
        { nod++; }

    return nod;
}

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