Submission #1319261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319261		ttamx	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	480 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int N=520;

int n;
vector<int> adj[N];
bool vis[N],bad[N];

int findEgg(int _n,vector<pair<int,int>> bridges){
    n=_n;
    for(auto [u,v]:bridges){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int cands=n;
    while(cands>1){
        queue<int> q;
        vector<int> to_ask;
        q.push(1);
        int cur=0;
        while(cur*2<cands){
            int u=q.front();
            q.pop();
            if(vis[u])continue;
            vis[u]=true;
            to_ask.push_back(u);
            if(!bad[u])cur++;
            for(auto v:adj[u]){
                if(!vis[v]){
                    q.push(v);
                }
            }
        }
        if(query(to_ask)){
            for(int i=1;i<=n;i++){
                if(!vis[i]){
                    bad[i]=true;
                }
            }
            cands=cur;
        }else{
            for(int i=1;i<=n;i++){
                if(vis[i]){
                    bad[i]=true;
                }
            }
            cands=cands-cur;
        }
        for(int i=1;i<=n;i++){
            vis[i]=false;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!bad[i]){
            ans=i;
        }
    }
    for(int i=1;i<=n;i++){
        adj[i].clear();
        bad[i]=false;
    }
    return ans;
}

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