oj.uz

Submission #916318

# Submission time Handle Problem Language Result Execution time Memory
916318 2024-01-25T16:20:01 Z rainboy Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 13 ms 1244 KB 
#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

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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Number of queries: 4
2 Correct 1 ms 344 KB Number of queries: 4
3 Correct 1 ms 344 KB Number of queries: 4
4 Correct 0 ms 440 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 720 KB Number of queries: 8
2 Correct 7 ms 720 KB Number of queries: 9
3 Correct 11 ms 1232 KB Number of queries: 9
4 Correct 10 ms 748 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 756 KB Number of queries: 9
2 Correct 13 ms 980 KB Number of queries: 9
3 Correct 11 ms 980 KB Number of queries: 9
4 Correct 12 ms 1244 KB Number of queries: 9