Submission #269752

#TimeUsernameProblemLanguageResultExecution timeMemory
269752theStaticMindEaster Eggs (info1cup17_eastereggs)C++14
71.60 / 100
15 ms384 KiB
#include<bits/stdc++.h> #define pb push_back #define ii pair<int,int> #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define INF 100000000000000000 #define modulo 1000000007 #define mod 998244353 using namespace std; #include "grader.h" vector<int> adj[1000]; vector<int> sub(1000); vector<bool> let(1000, false); void dfs(int x, int pre){ sub[x] = 1; for(auto y : adj[x]){ if(y == pre || !let[y]) continue; dfs(y, x); sub[x] += sub[y]; } } int find_centroid(int x, int pre, int sum){ for(auto y : adj[x]){ if(y == pre || !let[y]) continue; if(sub[y] > sum / 2) return find_centroid(y, x, sum); } return x; } void addall(int x, int pre, vector<int>& A){ A.pb(x); for(auto y : adj[x]){ if(y == pre || !let[y]) continue; addall(y, x, A); } } void split(int x, int pre, int s, vector<int>&L,vector<int>&R){ L.pb(x); R.pb(x); s--; for(auto y : adj[x]){ if(y == pre || !let[y]) continue; if(s >= sub[y]){ addall(y, x, L); s -= sub[y]; } else { addall(y, x, R); } } } int queryall(vector<int>& arr){ for(int i = 0; i < sz(arr) - 1; i++){ int x = arr[i]; if(query({x})) return x; } return arr.back(); } int solve(vector<int> comp){ for(auto x : comp) let[x] = true; if(comp.empty()) assert(0); dfs(comp[0], -1); int root = find_centroid(comp[0], -1, sub[comp[0]]); dfs(root, -1); if(sz(comp) <= 3) return queryall(comp); vector<int> left, right; split(root, -1, (sub[root] - 1) / 2 + 1, left, right); for(auto x : comp) let[x] = false; if(right.size() == 1){ return queryall(left); } if(left.size() == 1){ return queryall(right); } if(query(left)){ return solve(left); } else { return solve(right); } } void init(vector < pair < int, int > >& bridges){ static bool yes = true; if(yes) for(auto p : bridges){ adj[p.first].pb(p.second); adj[p.second].pb(p.first); } yes = false; } int findEgg (int N, vector < pair < int, int > > bridges) { init(bridges); vector<int> arr; for(int i = 1; i <= N; i++) arr.pb(i), let[i] = false; return solve(arr); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...