Submission #977905

#	Time	Username	Problem	Language	Result	Execution time	Memory
977905		AlphaMale06	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	17 ms	1112 KiB

eastereggs

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define pb push_back


const int M = 513;
vector<int> g[M];
vector<int> qry;
vector<int> nwnodes;

bool mark[M];
int cnt=0;
int query(vector<int> h);

void dfs(int v, int p){
    if(cnt==0)return;
    if(!mark[v])cnt--;
    qry.push_back(v);
    if(!mark[v])nwnodes.pb(v);
    mark[v]=1;
    for(int to : g[v]){
        if(to!=p)dfs(to, v);
    }
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    for(int i=1; i<=N; i++)g[i].clear();
    qry.clear();
    nwnodes.clear();
    for(int i=1; i<=N; i++)mark[i]=0;
    for(auto p : bridges){
        g[p.F].pb(p.S);
        g[p.S].pb(p.F);
    }
    if(N==1)return 1;
    int rest = N;
    for(int i=1; i<=9; i++){
        cnt = rest>>1;
        dfs(1, 1);
        int res = query(qry);
        if(res==1){
            for(int i=1; i<=N; i++)mark[i]=1;
            for(int e : nwnodes)mark[e]=0;
        }
        else{
            for(int e : qry)mark[e]=1;
        }
        nwnodes.clear();
        qry.clear();
        int cntm=0;
        for(int i=1; i<=N; i++){
            if(!mark[i])cntm++;
        }
        rest=cntm;
        if(cntm==1){
            for(int i=1; i<=N; i++){
                if(!mark[i])return i;
            }
        }
    }
}

Compilation message (stderr)

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

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