oj.uz

Submission #61656

# Submission time Handle Problem Language Result Execution time Memory
61656 2018-07-26T09:14:11 Z atoiz Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 101 ms 856 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Number of queries: 4
2 Correct 4 ms 484 KB Number of queries: 4
3 Correct 4 ms 484 KB Number of queries: 4
4 Correct 3 ms 484 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 484 KB Number of queries: 8
2 Correct 61 ms 676 KB Number of queries: 9
3 Correct 101 ms 784 KB Number of queries: 9
4 Correct 71 ms 836 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 836 KB Number of queries: 9
2 Correct 66 ms 856 KB Number of queries: 9
3 Correct 90 ms 856 KB Number of queries: 9
4 Correct 86 ms 856 KB Number of queries: 9