제출 #288359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288359		andreiomd	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	1 ms	520 KiB

eastereggs

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

using namespace std;

typedef pair < int, int > PII;

const int NMAX = ((1 << 9) + 5);
const int ROOT = 1;

int N, M;
vector < int > G[NMAX];

bool Sel[NMAX];
int V[(NMAX << 1)], cnt = 0;

vector < int > q;

void Reset (int N)
{
    for(int i = 1; i <= N; ++i)
    {
        if(!G[i].empty())
            G[i].clear();

        Sel[i] = 0;
    }

    cnt = 0;

    return;
}

void Add_Edge (int X, int Y)
{
    G[X].push_back(Y), G[Y].push_back(X);

    return;
}

void DFS (int Node)
{
    Sel[Node] = 1;

    V[++cnt] = Node;

    for(auto it : G[Node])
        if(!Sel[it])
        {
            DFS(it);

            V[++cnt] = Node;
        }

    return;
}

void Precalculation ()
{
    DFS(ROOT);

    return;
}

bool Ok (int pos)
{
    for(int i = 1; i <= N; ++i)
        Sel[i] = 0;

    if(!q.empty())
        q.clear();

    for(int i = 1; i <= pos; ++i)
    {
        if(!Sel[V[i]])
            q.push_back(V[i]);

        Sel[V[i]] = 1;
    }

    return query(q);
}

int Solve ()
{
    int Left = 1, Right = cnt;

    while(Left < Right)
    {
        int Mid = ((Left + Right) >> 1);

        if(Ok(Mid))
            Right = Mid;
        else
            Left = Mid + 1;
    }

    return V[Left];
}

int findEgg (int n, vector < PII > edges)
{
    Reset(n);

    for(auto it : edges)
        Add_Edge(it.first, it.second);

    Precalculation();

    return Solve();
}

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