oj.uz

Submission #288317

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

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.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 384 KB Number of queries: 12
2 Partially correct 1 ms 384 KB Number of queries: 12
3 Partially correct 1 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 10 ms 384 KB Number of queries: 22
2 Partially correct 19 ms 384 KB Number of queries: 35
3 Partially correct 25 ms 384 KB Number of queries: 44
4 Runtime error 2 ms 640 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 30 ms 384 KB Number of queries: 24
2 Partially correct 26 ms 384 KB Number of queries: 28
3 Runtime error 12 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -