Submission #435607

#	Time	Username	Problem	Language	Result	Execution time	Memory
435607		rainboy	Werewolf (IOI18_werewolf)	C++11	15 / 100	4037 ms	22212 KiB

werewolf

#include "werewolf.h"
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 200000;

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

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;
}

int find(int *ds, int i) {
	return ds[i] < 0 ? i : find(ds, ds[i]);
}

void join(int *ds, int *cc, int i, int j, int c) {
	i = find(ds, i);
	j = find(ds, j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j, cc[i] = c;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, cc[j] = c;
	}
}

int get(int *ds, int *cc, int i, int j, int mx) {
	int c;

	c = i;
	while (i != j)
		if (ds[i] >= 0 && (ds[j] < 0 || (cc[i] < cc[j]) == mx))
			c = cc[i], i = ds[i];
		else
			c = cc[j], j = ds[j];
	return c;
}

int ds1[N], cc1[N], ds2[N], cc2[N];

vi check_validity(int n, vi xx, vi yy, vi ss, vi ee, vi ll, vi rr) {
	int m = xx.size(), q = ss.size(), h, i, j, o;
	vi ok(q);

	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < m; h++)
		append(xx[h], yy[h]), append(yy[h], xx[h]);
	memset(ds1, -1, n * sizeof *ds1);
	for (i = 0; i < n; i++)
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (i > j)
				join(ds1, cc1, i, j, i);
		}
	memset(ds2, -1, n * sizeof *ds2);
	for (i = n - 1; i >= 0; i--)
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (i < j)
				join(ds2, cc2, i, j, i);
		}
	for (h = 0; h < q; h++)
		for (i = 0; i < n; i++)
			if (get(ds2, cc2, ss[h], i, 0) >= ll[h] && get(ds1, cc1, i, ee[h], 1) <= rr[h]) {
				ok[h] = 1;
				break;
			}
	return ok;
}

Compilation message (stderr)

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

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51