Submission #45398

#TimeUsernameProblemLanguageResultExecution timeMemory
45398bogdan10bosEaster Eggs (info1cup17_eastereggs)C++14
0 / 100
3 ms788 KiB
#include <bits/stdc++.h> using namespace std; //#define DEBUG #ifndef DEBUG #include "grader.h" #endif typedef pair<int, int> pii; int query (vector < int > h); int I, ord[1005]; vector<int> edg[1005]; void DFS(int nod, int fth) { ord[++I] = nod; for(auto nxt: edg[nod]) { if(nxt == fth) continue; DFS(nxt, nod); } } int myQuery(int pos) { vector<int> v; for(int i = 1; i <= pos; i++) v.push_back(i); return query(v); } int findEgg(int N, vector<pii> edges) { for(int i = 1; i <= N; i++) edg[i].clear(); for(auto e: edges) { edg[e.first].push_back(e.second); edg[e.second].push_back(e.first); } I = 0; DFS(1, 0); int st = 1, dr = N; while(st < dr) { int mij = st + (dr - st) / 2; if( myQuery(mij) ) dr = mij; else st = mij + 1; } return st; } #ifdef DEBUG 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 ("1.in", "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; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...