| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 243027 | umk | Easter Eggs (info1cup17_eastereggs) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "grader.h"
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e5+5;
int ck[N], nw[N], cnt, cur, num;
vector <int> adj[N], ans;
void dfs(int u, int p){
if (cur == num) return ;
if (ck[u]) cur++;
ans.pb(u);
for (int i=0; i<(int)adj[u].size(); i++){
int v = adj[u][i];
if (v == p) continue;
dfs(v, u);
}
}
int findEgg(int n, vector <pair <int, int> e){
for (int i=1; i<=n; i++) ck[i] = 1;
cnt = n;
for (int i=1; i<=n; i++) adj[i].clear();
for (int i=1; i<n; i++){
adj[e[i-1].fi].pb(e[i-1].se);
adj[e[i-1].se].pb(e[i-1].fi);
}
while (cnt != 1){
num = (cnt+1)>>1; cur = 0;
ans.clear();
dfs(1, 1);
if (query(ans)){
for (int i=1; i<=n; i++) nw[i] = 0;
for (int i=0; i<(int)ans.size(); i++) nw[ans[i]] = ck[ans[i]];
for (int i=1; i<=n; i++) ck[i] = nw[i];
cnt = num;
}
else{
for (int i=0; i<(int)ans.size(); i++) ck[ans[i]] = 0;
cnt -= num;
}
}
for (int i=1; i<=n; i++) if (ck[i]) return i;
}