Submission #631735

#	Time	Username	Problem	Language	Result	Execution time	Memory
631735		rainboy	Thousands Islands (IOI22_islands)	C++17	35 / 100	95 ms	21832 KiB

islands

#include "islands.h"
#include <variant>
#include <vector>
#include <stdlib.h>

using namespace std;

typedef vector<int> vi;
typedef variant<bool, vi> vbvi;

const int N = 100000, M = 200000;

int ij[M];
int *eh[N], eo[N], eo_[N], *fh[N], fo[N]; char deleted[N];

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

void dfs(int j) {
	if (deleted[j] || eo_[j])
		return;
	deleted[j] = 1;
	for (int o = fo[j]; o--; ) {
		int h = fh[j][o], i = j ^ ij[h];
		eo_[i]--, dfs(i);
	}
}

vbvi find_journey(int n, int m, vi ii, vi jj) {
	for (int i = 0; i < n; i++) {
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
		fh[i] = (int *) malloc(2 * sizeof *fh[i]);
	}
	for (int h = 0; h < m; h++) {
		int i = ii[h], j = jj[h];
		ij[h] = i ^ j;
		append(eh, eo, i, h), append(fh, fo, j, h), eo_[i]++;
	}
	for (int i = 0; i < n; i++)
		dfs(i);
	int s = 0;
	while (1) {
		if (eo_[s] == 0)
			return false;
		if (eo_[s] >= 2)
			return true;
		for (int o = eo[s]; o--; ) {
			int h = eh[s][o], i = s ^ ij[h];
			if (!deleted[i]) {
				eo_[s] = 0, dfs(s);
				s = i;
				break;
			}
		}
	}
	return true;
}

Compilation message (stderr)

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

• Subtask 1: 1.75 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 7.35 / 21
• Subtask 4: 8.399999999999999 / 24
• Subtask 5: 15.749999999999998 / 45