Submission #1226563

#TimeUsernameProblemLanguageResultExecution timeMemory
1226563jellybeanEaster Eggs (info1cup17_eastereggs)C++20
16 / 100
1 ms472 KiB
#include <bits/stdc++.h> #include "grader.h" using namespace std; #define pb push_back #define dd(x) cout<<#x<<" is "<<x<<endl; #define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl; #define dl(x) cout<<#x<<" is "<<endl; for(auto i:x) cout<<i<<' '; cout<<endl; #define fi first typedef pair<int,int> pii; vector<int>adj[600]; int par[600]; void dfs(int x, int p){ par[x] = p; for(auto i:adj[x]){ if(i==p)continue; dfs(i,x); } } int findEgg (int N, vector < pair < int, int > > bridges) { //if (query ({1})) return 1; int n = N; for(int i=1; i<=n; i++){ adj[i].clear(); } memset(par,0,sizeof(par)); for(int i=0; i<n-1; i++){ auto[u,v] = bridges[i]; adj[u].pb(v); adj[v].pb(u); } int root = -1; for(int i=1; i<=n; i++){ if(adj[i].size() != 1) root = i; } dfs(root,-1); queue<int>q; vector<int>v; if (query({root})) return root; v.pb(root); for(auto i: adj[root]) q.push(i); while(!q.empty()){ if(q.size() == 1){ int x = q.front(); q.pop(); v.pb(x); if(query(v)) return x; for(auto i: adj[x]) if(i!=par[x]) q.push(i); } else { int x = q.front(); q.pop(); int y = q.front(); q.pop(); //dd2(x,y) v.pb(x); v.pb(y); if(query(v)){ if(query({x})) return x; else return y; } for(auto i: adj[x]) if(i!=par[x]) q.push(i); for(auto i: adj[y]) if(i!=par[y]) q.push(i); } } return N; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...