Submission #1226574

#TimeUsernameProblemLanguageResultExecution timeMemory
1226574jellybeanEaster Eggs (info1cup17_eastereggs)C++20
0 / 100
0 ms492 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],dis[600]; void dfs(int x, int p){ //par[x] = p; for(auto i:adj[x]){ if(i==p)continue; dis[i]=dis[x]+1; dfs(i,x); } } void dfs2(int x, int p){ par[x] = p; for(auto i:adj[x]){ if(i==p)continue; dis[i]=dis[x]+1; dfs2(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)); memset(dis,0,sizeof(dis)); 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(1,-1); int root = -1, md = 0; for(int i=1; i<=n; i++) if(dis[i] > md) md = dis[i], root=i; memset(dis,0,sizeof(dis)); dfs2(root,-1); md = 0; int root1 = -1; for(int i=1; i<=n; i++) if(dis[i] > md) md = dis[i], root1=i; md/=2; for(int i=0; i<md; i++) root1 = par[root1]; //dd(root1) queue<int>q; vector<int>v; if (query({root1})) return root1; v.pb(root1); for(auto i: adj[root1]) 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...