oj.uz

Submission #287200

# Submission time Handle Problem Language Result Execution time Memory
287200 2020-08-31T13:29:34 Z andreiomd Easter Eggs (info1cup17_eastereggs) C++11
0 / 100
 3 ms 768 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

typedef pair < int, int > PII;

const int NMAX = 515;
const int ROOT = 1;

const int INF = 1e9;

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

int W[NMAX], Size;

int centroid;
bool used[NMAX];

static inline bool Ask (vector < int > Set)
{
    return query(Set);
}

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

    return;
}

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

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

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

    return;
}

static 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)
        {
            PII curr = Find(it, Node);

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

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

    return ans;
}

static inline void Scan (int Node, int Father, vector < int > &Container)
{
    Container.push_back(Node);

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

    return;
}

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

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

    PII Now = Find(Node, 0);
    centroid = Now.first;

    used[centroid] = 1;

    vector < int > V;
    V.push_back(centroid);

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

        return;
    }

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

            Scan(it, centroid, V);

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

                return;
            }
        }

    return;
}

int findEgg (int n, vector < PII > bridges)
{
    N = n;

    for(auto it : bridges)
    {
        int X = it.first, Y = it.second;

        Add_Edge(X, Y);
    }

    Go(ROOT);

    return ans;
}

Subtask #1
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB The found island is incorrect
2 Halted 0 ms 0 KB -

Subtask #2
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 #3
0 / 20.0

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