Submission #1319608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319608		ghammazhassan	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	488 KiB

eastereggs

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

using namespace std;

static int N, X, cntQ;
static vector < int > v[1009];

int query (vector < int > h);
const int MAXN=515;
vector<int>a[MAXN];
int findEgg(int n,vector<pair<int,int>>b){
    for (int i=1;i<=n;i++){
        a[i].clear();
    }
    for (auto [x,y]:b){
        a[x].push_back(y);
        a[y].push_back(x);
    }
    int c=n;
    vector<int>co(n+1);
    while (c>1){
        vector<int>vi(n+1);
        queue<int>o;
        o.push(1);
        vi[1]=1;
        vector<int>l;
        vector<int>op(n+1);
        int d=0;
        while (o.size()){
            int h=o.front();
            o.pop();
            l.push_back(h);
            op[h]=1;
            if (!co[h])d++;
            if (d==c/2)break;
            for (int i:a[h]){
                if (vi[i])continue;
                vi[i]=1;
                o.push(i);
            }
        }
        bool f=query(l);
        if (f){
            for (int i=1;i<=n;i++){
                if (!op[i]){
                    if (!co[i])c--;
                    co[i]=1;
                }
            }
        }
        else{
            for (int i=1;i<=n;i++){
                if (op[i]){
                    if (!co[i])c--;
                    co[i]=1;
                }
            }
        }
    }
    for (int i=1;i<=n;i++){
        if (!co[i])return i;
    }
    return 0;
}

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