제출 #1220553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220553		lukasuliashvili	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	21 ms	47452 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;

const int N = 2000005;
vector<int> vec[N], ans;
int fix[N];

vector<int> ask(int r) {
    return vector<int>(ans.begin(), ans.begin() + r + 1);
}

void dfs(int node, int par) {
    if (fix[node]) return;
    fix[node] = 1;
    ans.push_back(node);
    for (int to : vec[node]) {
        if (to != par) {
            dfs(to, node);
        }
    }
}

int findEgg(int N, vector<pair<int, int>> bridges) {
    ans.clear();
    for (int i = 0; i <= N; ++i) {
        vec[i].clear();
        fix[i] = 0;
    }
    for (auto [u, v] : bridges) {
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dfs(1, 0);
    int l = 0, r = ans.size() - 1, pas = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        vector<int> que = ask(mid);
        int egg = query(que);
        if (egg == 1) {
            pas = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return pas;
}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20