Submission #588581

#	Time	Username	Problem	Language	Result	Execution time	Memory
588581		Iwanttobreakfree	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	2 ms	592 KiB

eastereggs

#include <iostream>
#include <vector>
#include <set>
#include "grader.h"
using namespace std;
void dfs(int a,int par,vector<vector<int>>& g,vector<int>& pos,int& cnt,set<int>& q){
    if(cnt){
        q.insert(a+1);
        if(pos[a])cnt--;
    }else return;
    for(int x:g[a]){
        if(x==par)continue;
        dfs(x,a,g,pos,cnt,q);
        if(!cnt)return;
    }
}
int findEgg (int n,vector<pair<int,int>> bridges){
    vector<vector<int>> g(n,vector<int>());
    vector<int> pos(n,1);
    for(auto x:bridges){
        x.first--;x.second--;
        g[x.first].push_back(x.second);
        g[x.second].push_back(x.first);
    }
    int l=1,r=n;
    while(l<r){
        int mid=(r+l)/2;
        set<int> s;
        dfs(0,0,g,pos,mid,s);
        vector<int> q;
        for(auto x:s)q.push_back(x);
        bool egg=query(q);
        int y=0;
        for(int i=0;i<n;i++){
            if(pos[i]){
                if(egg&&s.find(i+1)==s.end())pos[i]=0;
                if(!egg&&s.find(i+1)!=s.end())pos[i]=0;
            }
            if(pos[i])y++;
        }
        r=y;
    }
    for(int i=0;i<n;i++)if(pos[i])return i;
    return -1;
}

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