Submission #1075138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075138		horiaboeriu	Easter Eggs (info1cup17_eastereggs)	C++17	60 / 100	17 ms	752 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define MAXN 1024
vector<int> v[MAXN + 1];
vector<int> islands;
int f[MAXN + 1], f2[MAXN + 1], deq[MAXN + 1];
int findEgg(int n, vector<pair<int, int>> bridges) {
    int nr, i, x, y, pr, ul, nr2, lung, rez;
    for (i = 1; i <= n; i++) {
        v[i].clear();
        f[i] = 0;
    }
    for (i = 0; i < n - 1; i++) {
        x = bridges[i].first;
        y = bridges[i].second;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    nr = n / 2;
    //in f[i] este 0 daca insula i poate avea oul si 1 daca stiu sigur ca nu il poate avea
    //in f2[i] este 0 daca nu am ajuns inca la insula i si 1 daca am pus insula i in vectorul islands la pasul curent
    while (nr > 0) {
        for (i = 1; i <= n; i++) {
            f2[i] = 0;
        }
        //fac un lee cu insulele, se poate si fill
        pr = nr2 = 0;
        ul = deq[0] = f2[1] = 1;
        islands.clear();
        islands.push_back(1);
        if (f[1] == 0) {
            nr2 = 1;//nr2 este numarul de insule care ar putea avea oul sunt in islands
        }
        while (pr != ul && nr2 < nr) {
            x = deq[pr];
            lung = v[x].size();
            i = 0;
            while (i < lung && nr2 < nr) {
                y = v[x][i];
                if (f2[y] == 0) {
                    islands.push_back(y);
                    nr2 += 1 - f[y];//creste daca in y poate fi oul
                    deq[ul] = y;
                    ul++;
                    f2[y] = 1;
                }
                i++;
            }
            pr++;
        }
        //in islands am adaugat nr inslue care ar putea avea oul si alte insuel care stiu ca nu il au
        rez = query(islands);
        if (rez == 0) {//daca pe acele insule nu este oul
            lung = islands.size();
            for (i = 0; i < lung; i++) {
                f[islands[i]] = 1;
            }
        } else {
            //apare in acelea deci sigur nu apare in celelalte
            for (i = 1; i <= n; i++) {
                if (f2[i] == 0) {//daca nu l-am pus in islands sigur nu e oul pe el
                    f[i] = 1;
                }
            }
        }
        nr /= 2;
    }
    i = 1;
    while (i <= n && f[i] > 0) {
        i++;
    }
    return i;
}

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