Submission #1101243

#TimeUsernameProblemLanguageResultExecution timeMemory
1101243Kirill22Easter Eggs (info1cup17_eastereggs)C++17
100 / 100
35 ms752 KiB
#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 (stderr)

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;
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...