oj.uz

Submission #827776

# Submission time Handle Problem Language Result Execution time Memory
827776 2023-08-16T18:20:10 Z PanosPask Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 18 ms 384 KB 
#include <bits/stdc++.h>
#include "grader.h"

#define pb push_back

using namespace std;

vector<vector<int>> adj_list;

vector<int> dfs_order;

void dfs(int node, int par)
{
    dfs_order.pb(node + 1);

    for (auto neigh : adj_list[node])
        if (neigh != par)
            dfs(neigh, node);
}

int findEgg(int N, vector<pair<int, int>> bridges)
{
    adj_list.clear();
    dfs_order.clear();

    adj_list.resize(N);

    for (int i = 0; i < N - 1; i++) {
        adj_list[bridges[i].first - 1].pb(bridges[i].second - 1);
        adj_list[bridges[i].second - 1].pb(bridges[i].first - 1);
    }

    dfs(0, -1);

    int l = -1;
    int r = N - 1;

    while (r > l + 1) {
        int mid = (l + r) / 2;
        if (query(vector<int>(dfs_order.begin(), dfs_order.begin() + mid + 1)))
            r = mid;
        else
            l = mid;
    }

    return dfs_order[r];
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Number of queries: 4
2 Correct 1 ms 208 KB Number of queries: 4
3 Correct 1 ms 208 KB Number of queries: 4
4 Correct 1 ms 208 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 8 ms 344 KB Number of queries: 9
3 Correct 14 ms 336 KB Number of queries: 9
4 Correct 11 ms 336 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Number of queries: 9
2 Correct 12 ms 356 KB Number of queries: 9
3 Correct 13 ms 336 KB Number of queries: 9
4 Correct 13 ms 360 KB Number of queries: 9