Submission #1215941

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

eastereggs

#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include "grader.h"
// #include <bits/stdc++.h>
#define in  cin
#define out cout

using namespace std;

// int care;
// int query(vector<int> h){
//     for(const int &x : h){
//         if(x == care) return 1;
//     }
//     return 0; // check pe foaie daca e conex
// }

int add[520]; // intr-un fel ce 'pondere' au (1 - > nou, 0 - > incercat)
int ramase;
vector<int> guess;
vector<int> g[520];
int news = 0;

void dfs(int nod, int f){
    guess.push_back(nod);
    news += add[nod];
    if(news == (ramase + 1) / 2) return;
    for(const int &x : g[nod]){
        if(x == f) continue;
        dfs(x, nod);
        if(news == (ramase + 1) / 2) return;
    }
}

int findEgg(int n, vector < pair < int, int > > bridges){
    for(int i = 0; i <= n; i++){
        add[i] = 1;
        g[i].clear();
    }
    ramase = n;
    news = 0;
    guess.clear();
    for(const pair<int, int> &x : bridges){
        g[x.first].push_back(x.second);
        g[x.second].push_back(x.first);
    }

    while(ramase > 1){
        dfs(1, -1);

        // cerr << "guess : ";
        // for(const int &x : guess) cerr << x << " ";
        // cerr << '\n';

        bool x = query(guess);
        // cerr << "  -- > x = " << x << " ramase = " << ramase << '\n';
        if(x == 0){
            for(const int &x : guess){
                if(add[x]) ramase--;
                add[x] = 0;
            }
        }else{
            sort(guess.begin(), guess.end());
            int it = 0;
            for(int i = 1; i <= n; i++){
                if(it < guess.size() && guess[it] == i){
                    it++; continue;
                }
                if(add[i]) ramase--;
                add[i] = 0;
            }
        }
        guess.clear();
        news = 0;
    }

    int x = 0;
    for(int i = 1; i <= n; i++){
        if(add[i]) x = i;
    }
    return x;
}

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