Submission #1099671

#TimeUsernameProblemLanguageResultExecution timeMemory
1099671tuannmEaster Eggs (info1cup17_eastereggs)C++17
0 / 100
153 ms131072 KiB
#include<bits/stdc++.h> #include "grader.h" #define ii pair<int, int> #define fi first #define se second #define pb push_back using namespace std; const int maxN = 520; vector<int> adj[maxN], dfs; /* bool isEgg[maxN]; bool query(vector<int> gg){ for(int i : gg) if(isEgg[i]) return true; return false; } */ void DFS(int u = 1, int p = 0){ dfs.pb(u); for(int v : adj[u]){ if(v == p) continue; DFS(v, u); } } int findEgg(int N, vector<ii> bridges){ for(auto [u, v] : bridges) adj[u].pb(v), adj[v].pb(u); DFS(); int ans = 0, l = 0, r = N - 1; while(l <= r){ int mid = l + r >> 1; if(query(vector<int> (dfs.begin(), dfs.begin() + mid))) ans = mid, r = mid - 1; else l = mid + 1; } return ans; } /* mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int l, int r){ return l + rd() % (r - l + 1); } int main(){ for(int __ = 1; __ <= 100; ++__){ int N = Rand(512, 512); vector<ii> bridges; for(int i = 2; i <= N; ++i) bridges.pb({i, Rand(1, i - 1)}); for(int i = 1; i <= N; ++i) isEgg[i] = Rand(0, 1); int gg = Rand(1, N); isEgg[gg] = true; int u = findEgg(N, bridges); for(int i = 1; i <= N; ++i) adj[i].clear(); if(!isEgg[u]){ cout << "Wrong on test " << __ << ":\n"; cout << N << "\n"; for(auto [x, y] : bridges) cout << x << " " << y << "\n"; for(int i = 1; i <= N; ++i) if(isEgg[i]) cout << i << " "; cout << "\nYour answer: " << u << ".\n"; return 0; } for(int i = 1; i <= N; ++i) isEgg[i] = false; } cout << "OK.\n"; } */

Compilation message (stderr)

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:45:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         int mid = l + r >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...