oj.uz

Submission #1101242

# Submission time Handle Problem Language Result Execution time Memory
1101242 2024-10-15T20:57:17 Z Kirill22 Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 3 ms 592 KB 
#include "bits/stdc++.h"

using namespace std;

int query(vector < int > islands);

int findEgg(int N, vector<pair<int, int>> bridges) {
    vector<vector<int>> g(N);
    for (auto [x, y] : bridges) {
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<int> life(N, 1);
    while (std::count(life.begin(), life.end(), 1) > 1) {
        vector<int> _query;
        int m = std::count(life.begin(), life.end(), 1) / 2;
        vector<int> dp(N);
        auto dfs = [&] (auto&& self, int v, int pr) {
            if (!m) {
                return;
            }
            if (life[v]) {
                m--;
            }
            _query.push_back(v + 1);
            for (auto u : g[v]) {
                if (u != pr) {
                    self(self, u, v);
                }
            }
        };
        dfs(dfs, 0, 0);
        int res = query(_query);
        if (!res) {
            for (auto& v : _query) {
                life[v] = 0;
            }
        } else {
            for (int i = 0; i < N; i++) {
                if (std::count(_query.begin(), _query.end(), i) == 0) {
                    life[i] = 0;
                }
            }
        }
    }
    int ans = 0;
    while (!life[ans]) {
        ans++;
    }
    return ans + 1;
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -