oj.uz

Submission #288348

# Submission time Handle Problem Language Result Execution time Memory
288348 2020-09-01T12:31:55 Z andreiomd Easter Eggs (info1cup17_eastereggs) C++11
0 / 100
 1 ms 640 KB 
#include <bits/stdc++.h>
#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;

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

    return;
}

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

    V[++cnt] = Node;

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

            V[++cnt] = Node;
        }

    return;
}

inline void Precalculation ()
{
    DFS(ROOT);

    return;
}

inline bool Ok (int pos)
{
    bitset < NMAX > mp;
    vector < int > q;

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

    return query(q);
}

inline 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)
{
    ++M;

    if(M == 1)
    {
        N = 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 512 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 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -