Submission #916318

#	Time	Username	Problem	Language	Result	Execution time	Memory
916318		rainboy	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	13 ms	1244 KiB

eastereggs

#include "grader.h"
#include <cstdlib>
#include <vector>

using namespace std;

typedef pair<int, int> pi;
typedef vector<pi> vpi;

const int N = 512;

int *ej[N], eo[N], qu[N], cnt;

void append(int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

void dfs(int p, int i) {
	qu[cnt++] = i + 1;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p)
			dfs(i, j);
	}
}

int findEgg(int n, vpi ij) {
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (int h = 0; h < n - 1; h++) {
		int i = ij[h].first - 1, j = ij[h].second - 1;
		append(i, j), append(j, i);
	}
	cnt = 0, dfs(-1, 0);
	for (int i = 0; i < n; i++)
		free(ej[i]);
	int lower = 0, upper = n;
	while (upper - lower > 1) {
		int h = (lower + upper) / 2;
		if (query(vector(qu, qu + h)))
			upper = h;
		else
			lower = h;
	}
	return qu[lower];
}

Compilation message (stderr)

eastereggs.cpp: In function 'void append(int, int)':
eastereggs.cpp:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

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