Submission #61656

#	Time	Username	Problem	Language	Result	Execution time	Memory
61656		atoiz	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	101 ms	856 KiB

eastereggs

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstdlib>
#include <string>
#include "grader.h"

using namespace std;

int curTime = 1, possibleChecks, maxChecks, possibleCnt;
vector<bool> visited, possible, checked;
vector<int> checks;
vector< vector<int> > graph;

void dfs(int u)
{
	if (possibleChecks >= maxChecks) return;
    if (visited[u]) return;
    visited[u] = 1;

    if (possible[u]) {
        ++possibleChecks;
    }
    checks.push_back(u);
    checked[u] = 1;

    for (int v : graph[u]) dfs(v);
}

int findEgg(int N, vector< pair<int, int> > bridges)
{
	graph.resize(N+1);
	for (auto a : bridges) {
        int u = a.first, v = a.second;
        graph[v].push_back(u);
        graph[u].push_back(v);
	}

	possibleCnt = N;
	possible.assign(N+1, 1);
    while (true) {
		if (possibleCnt == 1) {
            for (int u = 1; u <= N; ++u) {
				if (possible[u]) return u;
            }
		}

        possibleChecks = 0;
        maxChecks = possibleCnt / 2;
		visited.assign(N+1, 0);
		checked.assign(N+1, 0);
		checks.clear();

		dfs(1);
		int q = query(checks);
		if (q == 0) {
			possibleCnt = 0;
            for (int u = 1; u <= N; ++u) {
                if (checked[u]) {
                    possible[u] = 0;
                } else {
					if (possible[u]) ++possibleCnt;
                }
            }
		} else {
            possibleCnt = 0;
            for (int u = 1; u <= N; ++u) {
                if (!checked[u]) {
					possible[u] = 0;
                } else {
					if (possible[u]) ++possibleCnt;
                }
            }
		}
    }
    return 1;
}

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20