oj.uz

Submission #67629

# Submission time Handle Problem Language Result Execution time Memory
67629 2018-08-15T07:07:23 Z cdemirer Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 4 ms 732 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef pair<double, double> dodo;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

#include "grader.h"

bool poss[512];
vvi edges;
vi queryVector;

int parent[512];
int expand(int x, int rem) {
	if (poss[x]) {
		queryVector.pb(x);
		rem -= 1;
	}
	for (int i = 0; i < edges[x].size(); i++) {
		if (!rem) break;
		int y = edges[x][i];
		if (y == parent[x]) continue;
		parent[y] = x;
		rem = expand(y, rem);
	}
	return rem;
}

int findEgg (int N, vii bridges) {
	for (int i = 0; i < 512; i++) poss[i] = true;
	edges.clear();
	edges.resize(N);
	for (int i = 0; i < bridges.size(); i++) {
		edges[ bridges[i].first-1 ].pb(bridges[i].second-1);
		edges[ bridges[i].second-1 ].pb(bridges[i].first-1);
	}
	while (true) {
		//cerr << "currently possible: ";
		//for (int i = 0; i < N; i++) if (poss[i]) cerr << i << " ";
		//cerr << endl;
		
		queryVector.clear();
		int cnt = 0; for (int i = 0; i < N; i++) cnt += poss[i];
		int st = 0; for (int i = 0; i < N; i++) if (poss[i]) st = i;
		
		parent[st] = -1;
		expand(st, cnt/2);
		
		//cerr << "querying: ";
		//for (int i = 0; i < queryVector.size(); i++) cerr << queryVector[i] << " ";
		//cerr << endl;
		vi _qv(queryVector.size());
		for (int i = 0; i < queryVector.size(); i++) _qv[i] = queryVector[i]+1;
		int res = query(_qv);
		if (res) {
			for (int i = 0; i < 512; i++) poss[i] = false;
			for (int i = 0; i < queryVector.size(); i++) poss[queryVector[i]] = true;
		} else {
			for (int i = 0; i < queryVector.size(); i++) poss[queryVector[i]] = false;
		}
		
		//cerr << "now possible: ";
		//for (int i = 0; i < N; i++) if (poss[i]) cerr << i << " ";
		//cerr << endl;
		//cerr << endl;
		
		cnt = 0; for (int i = 0; i < N; i++) cnt += poss[i];
		if (cnt == 1) break;
	}
	for (int i = 0; i < N; i++) if (poss[i]) return i+1;
	exit(-1);
}

Compilation message

eastereggs.cpp: In function 'int expand(int, int)':
eastereggs.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges[x].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, vii)':
eastereggs.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < bridges.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~
eastereggs.cpp:59:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < queryVector.size(); i++) _qv[i] = queryVector[i]+1;
                   ~~^~~~~~~~~~~~~~~~~~~~
eastereggs.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < queryVector.size(); i++) poss[queryVector[i]] = true;
                    ~~^~~~~~~~~~~~~~~~~~~~
eastereggs.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < queryVector.size(); i++) poss[queryVector[i]] = false;
                    ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Number of queries: 4
2 Runtime error 3 ms 564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 704 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 732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -