oj.uz

Submission #487927

# Submission time Handle Problem Language Result Execution time Memory
487927 2021-11-17T06:33:49 Z Drew_ Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 15 ms 356 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

#define pb push_back

constexpr int MAX = 569;

bool dead[MAX] = {};
vector<int> adj[MAX], order;

void dfs(int node, int par)
{
    order.pb(node);
    for (int to : adj[node])
        if (to != par)
            dfs(to, node);
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    order.clear();
    for (int i = 1; i <= N; ++i)
        adj[i].clear(), dead[i] = false;

    for (auto &[u, v] : bridges)
        adj[u].pb(v), adj[v].pb(u);
    dfs(1, -1);

    while (N > 1)
    {
        int mid = N >> 1;

        int ctr = 0;
        vector<int> v;
        for (int x : order)
        {
            ctr += !dead[x];
            v.pb(x);
            
            if (ctr == mid)
                break;
        }

        if (query(v))
        {
            bool ok = false;
            for (int x : order)
            {
                if (ok)
                    dead[x] = true;

                if (x == v.back())
                    ok = true;
            }

            N = mid;
        }
        else
        {
            for (int x : v)
                dead[x] = true;
            N -= mid;
        }
    }

    for (int x : order)
        if (!dead[x])
            return x;

    return -1;
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Number of queries: 4
2 Correct 1 ms 200 KB Number of queries: 4
3 Correct 1 ms 200 KB Number of queries: 4
4 Correct 1 ms 200 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Number of queries: 8
2 Correct 9 ms 344 KB Number of queries: 9
3 Correct 15 ms 348 KB Number of queries: 9
4 Correct 13 ms 356 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 328 KB Number of queries: 9
2 Correct 12 ms 352 KB Number of queries: 9
3 Correct 14 ms 348 KB Number of queries: 9
4 Correct 13 ms 356 KB Number of queries: 9