| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1302605 | witek_cpp | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
vvi g;
vi ak;
int mid;
int ile_poszlo;
vi pyt;
// DFS: wchodzimy tylko do węzłów z ak==1 i dodajemy tylko takie węzły.
// zatrzymujemy gdy osiągniemy mid
void dfs_pyt_safe(int v, int p) {
if (ile_poszlo >= mid) return;
if (!ak[v]) return;
ile_poszlo++;
pyt.push_back(v);
if (ile_poszlo >= mid) return;
for (int u: g[v]) {
if (u == p) continue;
if (!ak[u]) continue;
dfs_pyt_safe(u, v);
if (ile_poszlo >= mid) return;
}
}
int findEgg(int n, vector<pii> kr) {
g.assign(n+1, {});
for (auto [u,v]: kr) {
g[u].push_back(v);
g[v].push_back(u);
}
ak.assign(n+1, 1);
unordered_set<int> zb;
for (int i=1;i<=n;i++) zb.insert(i);
while (zb.size() > 1) {
mid = int(zb.size())/2;
pyt.clear();
ile_poszlo = 0;
int start = *zb.begin();
// Jeśli start trafił na węzeł, który z jakiegoś powodu jest nieaktywny (powinno nie),
// to szukamy aktywnego startu w zb:
if (!ak[start]) {
bool found = false;
for (int x: zb) if (ak[x]) { start = x; found = true; break; }
if (!found) return *zb.begin(); // safety
}
dfs_pyt_safe(start, 0);
if (pyt.empty()) { // bezpieczeństwo — jeśli nic nie zebraliśmy, zwracamy element zb
return *zb.begin();
}
int val = query(pyt);
if (val) {
for (int i=1;i<=n;i++) ak[i]=0;
unordered_set<int> newzb;
for (int ele: pyt) { ak[ele]=1; newzb.insert(ele); }
zb = move(newzb);
} else {
for (int ele: pyt) {
zb.erase(ele);
ak[ele]=0;
}
}
}
return *zb.begin();
}