Submission #1150063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150063		dosts	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	496 KiB

eastereggs

#include "grader.h"
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

using namespace std;

vi edges[513],possible(513,0);
vi order;

void dfs(int node,int p) {
    order.push_back(node);
    for (auto it : edges[node]) {
        if (it == p) continue;
        dfs(it,node);
    }
}
int findEgg (int N, vector <pair<int,int>> bridges)
{
    order.clear();
    for (int i=1;i<=N;i++) edges[i].clear();
    for (int i=1;i<=N;i++) possible[i] = 1;
    for (auto it : bridges) {
        edges[it.ff].push_back(it.ss);
        edges[it.ss].push_back(it.ff);
    }
    dfs(1,1);
    int pos = N;
    while (pos > 1) {
        vi ask;
        int cnt = 0;
        for (int i=1;i<=N;i++) {
            if (possible[order[i-1]]) cnt++;
            ask.push_back(order[i-1]);
            if (cnt == pos/2) break;
        }
        int b = query(ask);
        if (!b) {
            for (auto it : ask) if (possible[it]) possible[it] = 0,pos--;
        }
        else {
            cnt = 0;
            for (int i=1;i<=N;i++) {
                if (possible[order[i-1]]) cnt++;
                if (cnt <= pos/2) continue;
                possible[order[i-1]] = 0;
            }
            pos-=pos/2;
        }
    }
    for (int i=1;i<=N;i++) if (possible[i]) return i;
}

Compilation message (stderr)

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

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