oj.uz

Submission #61651

# Submission time Handle Problem Language Result Execution time Memory
61651 2018-07-26T08:59:22 Z atoiz Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 4 ms 768 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;
        if (u > v) graph[v].push_back(u);
        else 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 8713409;
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -