Submission #1145803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145803		bbbiros	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	1 ms	1232 KiB

eastereggs

#include <vector>
#include <queue>
#include "grader.h"
#define endl '\n'
#define ll long long

using namespace std;
int n;
int used[1024];
vector <int> vo[1024];
vector <int> v[1024];
vector <int> vd[1024];
void reset()
{
    for(int i=1;i<514;i++)
        used[i]=0;
}
void bfs()
{
    reset();
    queue<int> q;
    q.push(1);
    used[1]=1;
    while(!q.empty())
    {
        int c=q.front();
        q.pop();
        for(int i=0;i<vo[c].size();i++)
        {
            int nb=vo[c][i];
            if(!used[nb])
            {
                used[nb]=1;
                v[c].push_back(nb);
                q.push(nb);
            }
        }
    }
}
vector<int> c;
void dfs(int beg)
{
    used[beg]=1;
    for(int i=0;i<c.size();i++)
    {
        vd[c[i]].push_back(beg);
    }
    c.push_back(beg);
    for(int i=0;i<v[beg].size();i++)
    {
        int nb=v[beg][i];
        if(!used[nb])
        {
            dfs(nb);
        }
    }
    c.pop_back();
}
int dnc(int beg)
{
    while(vd[beg].size()>1)
    {
        for(int i=0;i<v[beg].size();i++)
        {
            int nb=v[beg][i];
            //for(int j=0;j<vd[nb].size();j++)cout<<vd[nb][j]<<" ";
            //cout<<endl;
            if(query(vd[nb])==1)
            {
                beg=nb;
                break;
                continue;
            }
        }
        return beg;
    }
    return beg;
}
int findEgg (int N, vector < pair < int, int > > b)
{

    n=N;
    for(int i=1;i<=512;i++)
    {
        vo[i].clear();
        v[i].clear();
        vd[i].clear();
        vd[i].push_back(i);
    }
    reset();
    for(int i=0;i<b.size();i++)
    {
        vo[b[i].first].push_back(b[i].second);
        vo[b[i].second].push_back(b[i].first);
    }
    bfs();
    reset();
    dfs(1);
    return dnc(1);
}

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