Submission #631748

#	Time	Username	Problem	Language	Result	Execution time	Memory
631748		rainboy	Thousands Islands (IOI22_islands)	C++17	100 / 100	100 ms	22472 KiB

islands

#include "islands.h"
#include <variant>
#include <vector>
#include <stdlib.h>
#include <string.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);
	}
}

int pp[N], ff[N]; char visited[N];
vi hh;

void circle(int i, int rev) {
	if (visited[i]) {
		if (!rev) {
			int j = i;
			do
				hh.push_back(ff[j]);
			while ((j = pp[j]) != i);
		} else {
			static int qu[N];
			int j = i, cnt = 0;
			do
				qu[cnt++] = ff[j];
			while ((j = pp[j]) != i);
			while (cnt--)
				hh.push_back(qu[cnt]);
		}
		return;
	}
	hh.push_back(ff[i]), circle(pp[i], rev), hh.push_back(ff[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);
	static int qu[N];
	int u = 0, cnt = 0;
	while (1) {
		if (eo_[u] == 0)
			return false;
		if (eo_[u] >= 2)
			break;
		for (int o = eo[u]; o--; ) {
			int h = eh[u][o], i = u ^ ij[h];
			if (!deleted[i]) {
				qu[cnt++] = h;
				eo_[u] = 0, dfs(u);
				u = i;
				break;
			}
		}
	}
	memset(pp, -1, n * sizeof *pp), memset(ff, -1, n * sizeof *ff);
	int v = -1, f = -1;
	for (int i = 0; i < n; i++)
		if (!deleted[i])
			for (int o = eo[i]; o--; ) {
				int h = eh[i][o], j = i ^ ij[h];
				if (!deleted[j]) {
					if (pp[i] == -1)
						pp[i] = j, ff[i] = h;
					else if (i == u)
						v = j, f = h;
				}
			}
	int i;
	i = u;
	while (!visited[i])
		visited[i] = 1, i = pp[i];
	while (visited[i] == 1)
		visited[i] = 2, i = pp[i];
	for (i = 0; i < n; i++)
		if (visited[i] == 1)
			visited[i] = 0;
	i = v;
	while (!visited[i])
		visited[i] = 1, i = pp[i];
	for (int h = 0; h < cnt; h++)
		hh.push_back(qu[h]);
	if (visited[i] == 2) {
		for (i = 0; i < n; i++)
			if (visited[i] == 1)
				visited[i] = 0;
		circle(u, 0), hh.push_back(f), circle(v, 1), hh.push_back(f);
	} else {
		while (visited[i] == 1)
			visited[i] = 2, i = pp[i];
		for (i = 0; i < n; i++)
			if (visited[i] == 1)
				visited[i] = 0;
		circle(u, 0), hh.push_back(f), circle(v, 0), hh.push_back(f);
		circle(u, 1), hh.push_back(f), circle(v, 1), hh.push_back(f);
	}
	for (int h = cnt - 1; h >= 0; h--)
		hh.push_back(qu[h]);
	return hh;
}

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 45 / 45