| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 87064 | 2018-11-29T10:40:57 Z | report | Easter Eggs (info1cup17_eastereggs) | C++14 | 0 ms | 0 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include "grader.h"
using namespace std;
void computeUnmarkedComponent(
int n,
const vector<int> &marked,
const vector<vector<int>> &tree,
vector<int> &res) {
int treeSize = (int)tree.size();
queue<int> q;
vector<bool> visited(treeSize);
q.push(1);
visited[1] = true;
int unmarkedCnt = 0;
while (!q.empty() && unmarkedCnt < n) {
int u = q.front();
q.pop();
unmarkedCnt += !marked[u];
res.push_back(u);
for (int v : tree[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
sort(res.begin(), res.end());
}
int findEgg(int N, vector<pair<int, int>> bridges) {
vector<int> marked(N + 1);
vector<vector<int>> tree(N + 1, vector<int>());
for (const pair<int, int> &edge : bridges) {
tree[edge.first].push_back(edge.second);
tree[edge.second].push_back(edge.first);
}
vector<int> allNodes;
for (int i = 1; i <= N; i++) allNodes.push_back(i);
int unmarkedCnt = N;
while (true) {
if (unmarkedCnt == 1) {
for (int i = 1; i <= N; i++) {
if (!marked[i]) return i;
}
break;
}
vector<int> component;
computedUnmarkedComponent(unmarkedCnt / 2, marked, tree, component);
vector<int> toMark;
if (query(component)) {
toMark.resize(N - (int)component.size());
set_difference(allNodes.begin(), allNodes.end(),
component.begin(), component.end(), toMark.begin());
unmarkedCnt /= 2;
} else {
toMark = component;
unmarkedCnt -= unmarkedCnt / 2;
}
for (int n : toMark) {
marked[n] = true;
}
}
return 0;
}