oj.uz

Submission #45403

# Submission time Handle Problem Language Result Execution time Memory
45403 2018-04-13T08:16:29 Z bogdan10bos Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 21 ms 652 KB 
#include <bits/stdc++.h>

using namespace std;

#include "grader.h"

typedef pair<int, int> pii;

int I, ord[1005];
vector<int> edg[1005];
void DFS(int nod, int fth)
{
    ord[++I] = nod;
    for(auto nxt: edg[nod])
    {
        if(nxt == fth)  continue;
        DFS(nxt, nod);
    }
}

int myQuery(int pos)
{
    vector<int> v;
    for(int i = 1; i <= pos; i++)
        v.push_back(ord[i]);
    return query(v);
}

int findEgg(int N, vector<pii> edges)
{
    for(int i = 1; i <= N; i++) edg[i].clear();

    for(auto e: edges)
    {
        edg[e.first].push_back(e.second);
        edg[e.second].push_back(e.first);
    }

    I = 0;
    DFS(1, 0);

    int st = 1, dr = N;
    while(st < dr)
    {
        int mij = st + (dr - st) / 2;
        if( myQuery(mij) )
            dr = mij;
        else
            st = mij + 1;
    }
    return ord[st];
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 244 KB Number of queries: 4
2 Correct 2 ms 308 KB Number of queries: 4
3 Correct 3 ms 344 KB Number of queries: 4
4 Correct 2 ms 360 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 420 KB Number of queries: 8
2 Correct 11 ms 548 KB Number of queries: 9
3 Correct 18 ms 548 KB Number of queries: 9
4 Correct 18 ms 548 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 624 KB Number of queries: 9
2 Correct 15 ms 652 KB Number of queries: 9
3 Correct 15 ms 652 KB Number of queries: 9
4 Correct 21 ms 652 KB Number of queries: 9