Submission #958798

#	Time	Username	Problem	Language	Result	Execution time	Memory
958798		LaviniaTornaghi	Easter Eggs (info1cup17_eastereggs)	C++17	26.40 / 100	18 ms	532 KiB

eastereggs

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

int query(vector<int> h);

int findEgg (int N, vector < pair < int, int > > bridges){
    vector<vector<int>> t(N+1);
    for(auto [a,b]:bridges){
        t[a].push_back(b);
        t[b].push_back(a);
    }
    set<int> s;
    for(int i=1;i<=N;i++) s.insert(i);

    while(s.size()>1){
        vector<bool>vis(N+1);
        set<int> e;
        function<void(int)> dfs = [&] (int nd){
            vis[nd]=1;
            if(e.size()<(s.size()/2)) e.insert(nd);
            else return;
            for(auto u : t[nd])
                if(!vis[u] && s.find(u)!=s.end())
                    dfs(u);
        };
        dfs(*s.begin());
        if(!query(vector(e.begin(), e.end()))){
            set<int> m;
            for(auto x : s) 
                if(e.find(x)==e.end())
                    m.insert(x);
            s = m;
        }else 
            s=e;
    }
    return *s.begin();
}

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