Submission #1226680

#TimeUsernameProblemLanguageResultExecution timeMemory
1226680jellybeanEaster Eggs (info1cup17_eastereggs)C++20
100 / 100
8 ms520 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],a[600]; int cnt; void dfs(int x, int p){ par[x] = p; a[cnt] = x; cnt++; for(auto i:adj[x]){ if(i==p)continue; dis[i]=dis[x]+1; dfs(i,x); } } int findEgg (int N, vector < pair < int, int > > bridges) { //if (query ({1})) return 1; cnt=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); } dfs(1,-1); int l=0, h=n; //if contain we move high down if not we move low up while(h-l > 1){ int mid = (h+l)/2; vector<int>v; for(int i=1; i<=mid; i++) v.pb(a[i]); if(query(v)) h = mid; else l = mid; } return a[h]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...