oj.uz

Submission #288315

# Submission time Handle Problem Language Result Execution time Memory
288315 2020-09-01T12:04:48 Z andreiomd Easter Eggs (info1cup17_eastereggs) C++11
0 / 100
 16 ms 512 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, 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.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 256 KB Number of queries: 12
2 Partially correct 1 ms 384 KB Number of queries: 12
3 Partially correct 2 ms 384 KB Number of queries: 11
4 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 384 KB Number of queries: 22
2 Partially correct 14 ms 384 KB Number of queries: 35
3 Partially correct 13 ms 384 KB Number of queries: 44
4 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 16 ms 384 KB Number of queries: 24
2 Partially correct 14 ms 384 KB Number of queries: 28
3 Runtime error 7 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -