Submission #288324

#	Time	Username	Problem	Language	Result	Execution time	Memory
288324		andreiomd	Easter Eggs (info1cup17_eastereggs)	C++11	0 / 100	18 ms	512 KiB

eastereggs

#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;

vector < int > G[NMAX];

int W[NMAX], Size, centroid, ans;
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] && !ans)
        {
            V.clear();
            DFS_2(it, centroid);

            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
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20