Submission #67633

#	Time	Username	Problem	Language	Result	Execution time	Memory
67633		cdemirer	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	42 ms	564 KiB

eastereggs

#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) {
	queryVector.pb(x);
	if (poss[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) {
			vi ok;
			for (int i = 0; i < queryVector.size(); i++) if (poss[queryVector[i]]) ok.pb(queryVector[i]);
			for (int i = 0; i < 512; i++) poss[i] = false;
			for (int i = 0; i < ok.size(); i++) poss[ok[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 (stderr)

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++) if (poss[queryVector[i]]) ok.pb(queryVector[i]);
                    ~~^~~~~~~~~~~~~~~~~~~~
eastereggs.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < ok.size(); i++) poss[ok[i]] = true;
                    ~~^~~~~~~~~~~
eastereggs.cpp:67: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: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20