oj.uz

Submission #435607

# Submission time Handle Problem Language Result Execution time Memory
435607 2021-06-23T13:21:52 Z rainboy Werewolf (IOI18_werewolf) C++11
15 / 100
 4000 ms 22212 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 83 ms 640 KB Output is correct
11 Correct 136 ms 756 KB Output is correct
12 Correct 429 ms 724 KB Output is correct
13 Correct 77 ms 744 KB Output is correct
14 Correct 134 ms 748 KB Output is correct
15 Correct 175 ms 844 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4037 ms 22212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 83 ms 640 KB Output is correct
11 Correct 136 ms 756 KB Output is correct
12 Correct 429 ms 724 KB Output is correct
13 Correct 77 ms 744 KB Output is correct
14 Correct 134 ms 748 KB Output is correct
15 Correct 175 ms 844 KB Output is correct
16 Execution timed out 4037 ms 22212 KB Time limit exceeded
17 Halted 0 ms 0 KB -