Submission #1165866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165866		AlgorithmWarrior	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	11 ms	508 KiB

eastereggs

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

using namespace std;

void dfs(int nod,int tata,int& sum,vector<int>&nodes,vector<vector<int>>&tree,vector<int>&sol){
    nodes.push_back(nod);
    sum-=sol[nod];
    for(auto fiu : tree[nod])
        if(fiu!=tata && sum)
            dfs(fiu,nod,sum,nodes,tree,sol);
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    vector<vector<int>>tree(N+5);
    for(auto [u,v] : bridges){
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    vector<int>sol(N+5,1);
    int cauta=N;
    int i;
    while(cauta>1){
        int sum=cauta/2;
        vector<int>nodes;
        dfs(1,0,sum,nodes,tree,sol);
        if(query(nodes)){
            for(auto nd : nodes)
                if(sol[nd]==1)
                    sol[nd]=2;
            for(i=1;i<=N;++i)
                if(sol[i]==1)
                    sol[i]=0;
            for(i=1;i<=N;++i)
                if(sol[i]==2)
                    sol[i]=1;
            cauta/=2;
        }
        else{
            for(auto nd : nodes)
                sol[nd]=0;
            cauta-=cauta/2;
        }
    }
    for(i=1;i<=N;++i)
        if(sol[i])
            return i;
}

Compilation message (stderr)

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

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