Submission #1257228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257228		FernandoJC07	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	6 ms	484 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define vi vector<int>
#define vii vector<vi>
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vpii vector<pii>
#define forn(i, n) for(int i = 0; i<n; ++i)
#define For(i, a, n) for(int i = a; i<n; ++i)
using namespace std;

int findEgg(int N, vpii bridges){
    vector<vi> adj(N+1);
    for(auto x: bridges){
        adj[x.ff].pb(x.ss);
        adj[x.ss].pb(x.ff);
    }
    int Sz = N;
    vi vst(N+1, 1);
    while(Sz>1){
        int sz = Sz/2;
        For(i, 1, N+1){
            if(vst[i]){
                vi vst2(N+1, 0);
                int zs = sz;
                vi laputa;
                queue<int> q;
                zs--;
                vst2[i] = 1;
                q.push(i);
                while(!q.empty()){
                    int u = q.front(); q.pop();
                    laputa.pb(u);
                    for(int x: adj[u]){
                        if(zs && !vst2[x]){
                            zs -= vst[x];
                            vst2[x] = 1;
                            q.push(x);
                        }
                    }
                }
                int val = query(laputa);
                vi red;
                for(int x: laputa) if(vst[x]) red.pb(x);
                //mos(laputa);
                //dbg(val);
                if(!val) {
                    for(int& x: red) vst[x] = 0;
                    Sz -= sz;
                }
                else { fill(vst.begin(), vst.end(), 0); for(int x: red) vst[x] = 1; Sz = sz;}
                break;
            }
        }
    }
    For(i, 1, N+1) if(vst[i]) return i;
}

Compilation message (stderr)

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

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