oj.uz

Submission #1101243

# Submission time Handle Problem Language Result Execution time Memory
1101243 2024-10-15T20:59:53 Z Kirill22 Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 35 ms 752 KB 
#include "bits/stdc++.h"

using namespace std;

int query(vector < int > islands);

int findEgg(int N, vector<pair<int, int>> bridges) {
    vector<vector<int>> g(N);
    for (auto [x, y] : bridges) {
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<int> life(N, 1);
    int iter = 0;
    while (std::count(life.begin(), life.end(), 1) > 1) {
        vector<int> _query;
        int m = std::count(life.begin(), life.end(), 1) / 2;
        vector<int> dp(N);
        auto dfs = [&] (auto&& self, int v, int pr) {
            if (!m) {
                return;
            }
            if (life[v]) {
                m--;
            }
            _query.push_back(v + 1);
            for (auto u : g[v]) {
                if (u != pr) {
                    self(self, u, v);
                }
            }
        };
        dfs(dfs, 0, 0);
        int res = query(_query);
        if (!res) {
            for (auto& v : _query) {
                life[v - 1] = 0;
            }
        } else {
            for (int i = 0; i < N; i++) {
                if (std::count(_query.begin(), _query.end(), i + 1) == 0) {
                    life[i] = 0;
                }
            }
        }
    }
    int ans = 0;
    while (!life[ans]) {
        ans++;
    }
    return ans + 1;
}

//static int N, X, cntQ;
//static vector < int > v[1009];
//
//int query (vector < int > h)
//{
//    cntQ ++;
//    int ap[1009];
//    if (h.empty ()) return 0;
//    for (int i=1; i<=N; i++)
//        ap[i] = 0;
//    for (auto it = h.begin (); it != h.end (); it ++)
//        ap[*it] = 1;
//    queue < int > cc;
//    cc.push (h[0]), ap[h[0]] = 2;
//    while (!cc.empty ())
//    {
//        int nod = cc.front ();
//        cc.pop ();
//        for (auto it = v[nod].begin (); it != v[nod].end (); it ++)
//            if (ap[*it] == 1)
//                ap[*it] = 2, cc.push (*it);
//    }
//    for (int i=1; i<=N; i++)
//        if (ap[i] == 1) return -1;
//    for (auto it = h.begin (); it != h.end (); it ++)
//        if (*it == X) return 1;
//    return 0;
//}
//
//int main ()
//{
////    freopen ("input", "r", stdin);
////freopen ("output", "w", stdout);
//
//    scanf ("%d", &N);
//    int Queries;
//    vector < pair < int, int > > param;
//    for (int i=1; i<N; i++)
//    {
//        int x, y;
//        scanf ("%d %d", &x, &y);
//        v[x].push_back (y);
//        v[y].push_back (x);
//        param.push_back ({x, y});
//    }
//    scanf ("%d", &Queries);
//    while (Queries --)
//    {
//        scanf ("%d", &X), cntQ = 0;
//        int Y = findEgg (N, param);
//        if (X != Y)
//        {
//            printf ("WA %d instead of %d\n", Y, X);
//            return 0;
//        }
//        printf ("OK %d\n", cntQ);
//    }
//    return 0;
//}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:15:9: warning: unused variable 'iter' [-Wunused-variable]
   15 |     int iter = 0;
      |         ^~~~

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 336 KB Number of queries: 8
2 Correct 19 ms 336 KB Number of queries: 9
3 Correct 35 ms 336 KB Number of queries: 9
4 Correct 30 ms 496 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 592 KB Number of queries: 9
2 Correct 30 ms 584 KB Number of queries: 9
3 Correct 35 ms 592 KB Number of queries: 9
4 Correct 33 ms 752 KB Number of queries: 9