제출 #288317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288317		andreiomd	Easter Eggs (info1cup17_eastereggs)	C++11	0 / 100	30 ms	640 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;

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

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

vector < int > V;

map < int, int > Ord;

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, centroid);

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

                return;
            }
        }

    return;
}

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

    map < int, bool > mp;
    for(auto it : edges)
        mp[it.first] = 1, mp[it.second] = 1;
    int cnt = 0;
    for(auto it : mp)
        Ord[it.first] = (++cnt);

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

    Go(ROOT);

    return ans;
}

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