oj.uz

Submission #288359

# Submission time Handle Problem Language Result Execution time Memory
288359 2020-09-01T12:41:19 Z andreiomd Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 1 ms 520 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -