# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
525621 | 2022-02-12T06:56:47 Z | tudor | Easter Eggs (info1cup17_eastereggs) | C++17 | 21 ms | 456 KB |
#include <iostream> #include <vector> #include "grader.h" using namespace std; const int nmax = 512; int n; vector < pair < int, int > > bridges; vector < int > g[nmax + 1]; vector < int > ord; vector < int > q; void dfs ( int node, int parent ) { ord.push_back ( node ); for ( int i = 0; i < g[node].size (); i++ ) if ( g[node][i] != parent ) dfs ( g[node][i], node ); } /** int query ( vector < int > islands ) { int r; cin >> r; return r; } **/ int findEgg ( int n, vector < pair < int, int > > bridges ) { ord.clear (); for ( int i = 1; i <= n; i++ ) g[i].clear (); for ( int i = 0; i < n - 1; i++ ) { g[bridges[i].first].push_back ( bridges[i].second ); g[bridges[i].second].push_back ( bridges[i].first ); } dfs ( 1, 0 ); int st = 1, dr = n - 1, mij, poz = 0; while ( st <= dr ) { int mij = st + ( dr - st ) / 2; q.clear (); for ( int i = 0; i <= mij; i++ ) q.push_back ( ord[i] ); if ( query ( q ) == 1 ) dr = mij - 1, poz = mij; else st = mij + 1; } return ord[poz]; } /* int main() { cin >> n; bridges.resize ( n ); for ( int i = 0; i < n - 1; i++ ) cin >> bridges[i].first >> bridges[i].second; cout << findEgg ( n, bridges ); return 0; } */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 456 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 336 KB | Number of queries: 8 |
2 | Correct | 11 ms | 332 KB | Number of queries: 9 |
3 | Correct | 15 ms | 328 KB | Number of queries: 9 |
4 | Correct | 13 ms | 336 KB | Number of queries: 9 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 356 KB | Number of queries: 9 |
2 | Correct | 14 ms | 328 KB | Number of queries: 9 |
3 | Runtime error | 7 ms | 456 KB | Execution killed with signal 6 |
4 | Halted | 0 ms | 0 KB | - |