oj.uz

Submission #288310

# Submission time Handle Problem Language Result Execution time Memory
288310 2020-09-01T12:02:10 Z andreiomd Easter Eggs (info1cup17_eastereggs) C++11
0 / 100
 17 ms 540 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;

const int INF = 1e9;

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

int W[NMAX], Size, centroid;
bool used[NMAX];

vector < int > V;

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

    return;
}

inline void Reset (int N)
{
    ans = 0;

    for(int i = 1; i <= N; ++i)
        used[i] = 0, W[i] = 0, G[i].clear();

    return;
}

inline void DFS_1 (int Node, int Father)
{
    W[Node] = 1;

    for(auto it : G[Node])
        if(!used[it] && it != Father)
        {
            DFS_1(it, Node);

            W[Node] += W[it];
        }

    return;
}

inline int MAX (int a, int b)
{
    return ((a > b) ? a : b);
}

inline PII Find (int Node, int Father)
{
    int Max = Size - W[Node];
    PII ans = {0, INF};

    for(auto it : G[Node])
        if(!used[it] && it != Father)
        {
            Max = MAX(Max, W[it]);

            PII curr = Find(it, Node);

            if(curr.second < ans.second)
                ans = curr;
        }

    if(Max < ans.second)
        ans = {Node, Max};

    return ans;
}

inline void DFS_2 (int Node, int Father)
{
    V.push_back(Node);

    for(auto it : G[Node])
        if(!used[it] && it != Father)
            DFS_2(it, Node);

    return;
}

inline void Go (int Node)
{
    if(ans)
        return;

    DFS_1(Node, 0), Size = W[Node];

    int centroid = Find(Node, 0).first;

    used[centroid] = 1;

    V.clear(), V.push_back(centroid);

    if(query(V))
    {
        ans = centroid;

        return;
    }

    for(auto it : G[centroid])
        if(!used[it])
        {
            V.clear();

            DFS_2(it, Node);

            if(query(V))
            {
                Go(it);

                return;
            }
        }

    return;
}

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

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

    Go(ROOT);

    return ans;
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 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 3 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 Partially correct 17 ms 384 KB Number of queries: 24
2 Runtime error 6 ms 540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -