제출 #1283426

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

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int n, cnt = 1, f, vis[1000];
vector<int> g[1000], ask = {1};
set<int> can;
void dfs(int u){
    if(u != 1 && !vis[u]){
        ask.push_back(u);
        //cout << u << ' ';
    }
    vis[u] = 1;
    for(auto v : g[u]){
        if(!vis[v] && cnt != f && can.find(v) != can.end()){
            ++cnt;
            dfs(v);
        }
    }
}
int findEgg (int N, vector < pair < int, int > > e){
    memset(vis, 0, sizeof vis);
    cnt = 1;
    ask = {1};
    can.clear();
    for(int i = 0;i<1000;i++){
        g[i].clear();
    }
    n = N;
    for(auto [u, v] : e){
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1;i<=n;i++) can.insert(i);
    int l = 1, r = n;
    bool in = false;
    int fr = 1;
    while(1){
        if(!in){
            f = (l + r - 1) / 2;
            for(auto x : ask){
                can.erase(x);
            }
            for(auto x : ask){
                dfs(x);
            }
            if(fr) can.insert(1);
            in = query(ask);
            fr = 0;
            if(!in){
                l = f + 1;
            }
        }else{
            r = f;
            f = (l + r - 1) / 2;
            //cout << l << ' ' << r << '\n';
            cnt = f;
            for(int i = 1;i<=n;i++){
                bool g = 0;
                for(auto x : ask) if(x == i) g = 1;
                if(!g) can.erase(i);
            }
            while(ask.size() > f) vis[ask.back()] = 0, ask.pop_back();
            in = query(ask);
        }
        // for(auto x : ask) cout << x << ' ';
        // cout << '\n';
        // for(auto x : can) cout << x << ' ';
        // cout << '\n';
        if(can.size() == 1) return *can.begin();
    }
    return 0;
}

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