Submission #1109507

#TimeUsernameProblemLanguageResultExecution timeMemory
1109507the_coding_poohEaster Eggs (info1cup17_eastereggs)C++14
0 / 100
117 ms131072 KiB
#include <bits/stdc++.h> // #define LOCAL #define uwu return using namespace std; const int SIZE = 513; vector <int> graph[SIZE]; #define fs first #define sc second #ifdef LOCAL int findEgg(int N, vector<pair<int, int>> bridges); int a; int query(vector <int> vec){ for(auto i:vec){ if(i == a) return 1; } return 0; } int main(){ int N; cin >> N >> a; vector <pair<int, int>> edges; for (int i = 1, u, v; i < N; i++){ cin >> u >> v; edges.push_back({u, v}); } int tmp = findEgg(N, edges); if(tmp == a) cout << "AC\n"; else{ cout << "WA\n"; cout << tmp << '\n'; } uwu 0; } #else int query(vector < int > islands); #endif void dfs(vector <int>& vertices, int nd, int rt){ vertices.push_back(nd); for(auto i:graph[nd]){ if(i != rt) dfs(vertices, i, nd); } return; } int findEgg (int N, vector <pair<int, int>> bridges){ for(auto i:bridges){ graph[i.fs].push_back(i.sc); graph[i.sc].push_back(i.fs); } vector <int> vertices; dfs(vertices, 1, 0); int L = 0, R = N - 1, M; while(L != R){ vector <int> tmp = vertices; M = (L + R) / 2; tmp.erase(tmp.begin() + M + 1, tmp.end()); if(query(tmp)) R = M; else L = M + 1; } uwu vertices[L]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...