oj.uz

Submission #1075143

# Submission time Handle Problem Language Result Execution time Memory
1075143 2024-08-25T19:00:34 Z horiaboeriu Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 16 ms 752 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define MAXN 512
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 = 0;
        for (i = 1; i <= n; i++) {
            nr += 1 - f[i];
        }
        nr /= 2;
    }
    i = 1;
    while (i <= n && f[i] > 0) {
        i++;
    }
    return i;
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Number of queries: 4
2 Correct 1 ms 344 KB Number of queries: 4
3 Correct 1 ms 344 KB Number of queries: 4
4 Correct 1 ms 344 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Number of queries: 8
2 Correct 7 ms 344 KB Number of queries: 9
3 Correct 13 ms 740 KB Number of queries: 9
4 Correct 9 ms 344 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 600 KB Number of queries: 9
2 Correct 10 ms 344 KB Number of queries: 9
3 Correct 16 ms 752 KB Number of queries: 9
4 Correct 10 ms 344 KB Number of queries: 9