oj.uz

Submission #435665

# Submission time Handle Problem Language Result Execution time Memory
435665 2021-06-23T14:28:21 Z rainboy Werewolf (IOI18_werewolf) C++11
100 / 100
 852 ms 76540 KB 
#include "werewolf.h"
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 200000, Q = 200000;

int t;

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

void append(int **ej, int *eo, 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 ds[N], cc[N];

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

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

int ta[2][N], tb[2][N], time;

void dfs(int i) {
	int o;

	ta[t][i] = time++;
	for (o = 0; o < fo[i]; o++) {
		int j = fj[i][o];

		dfs(j);
	}
	tb[t][i] = time;
}

int ll_[2][Q], rr_[2][Q];

void get_segment(int i, int c, int *l, int *r) {
	int lower, upper, o;

	while (ds[i] >= 0 && cc[i] >= c)
		i = ds[i];
	lower = -1, upper = fo[i];
	while (upper - lower > 1) {
		int o = (lower + upper) / 2;

		if (cc[fj[i][o]] >= c)
			lower = o;
		else
			upper = o;
	}
	*l = ta[t][i], *r = lower == -1 ? ta[t][i] + 1 : tb[t][fj[i][lower]];
}

int ft[N];

void update(int i, int n) {
	while (i < n) {
		ft[i]++;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int idx[N], kk[Q];

void solve(int n) {
	int i, o;

	for (i = 0; i < n; i++) {
		update(idx[i], n);
		for (o = eo[i]; o--; ) {
			int h_ = ej[i][o], h = h_ >> 1;

			kk[h] += (query(rr_[1][h] - 1) - query(ll_[1][h] - 1)) * ((h_ & 1) == 0 ? -1 : 1);
		}
	}
}

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, h_, i, j, o, tmp;
	vi ok(q);

	for (t = 0; t < 2; t++) {
		for (i = 0; i < n; i++) {
			ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
			fj[i] = (int *) malloc(2 * sizeof *fj[i]), fo[i] = 0;
		}
		for (h = 0; h < m; h++)
			append(ej, eo, xx[h], yy[h]), append(ej, eo, yy[h], xx[h]);
		memset(ds, -1, n * sizeof *ds);
		for (i = n - 1; i >= 0; i--)
			for (o = eo[i]; o--; ) {
				j = ej[i][o];
				if (i < j)
					join(i, j, i);
			}
		time = 0;
		for (i = 0; i < n; i++)
			if (ds[i] < 0)
				dfs(i);
		for (h = 0; h < m; h++)
			xx[h] = n - 1 - xx[h], yy[h] = n - 1 - yy[h];
		for (h = 0; h < q; h++)
			get_segment(ss[h], ll[h], &ll_[t][h], &rr_[t][h]);
		for (h = 0; h < q; h++) {
			tmp = ss[h], ss[h] = n - 1 - ee[h], ee[h] = n - 1 - tmp;
			tmp = ll[h], ll[h] = n - 1 - rr[h], rr[h] = n - 1 - tmp;
		}
	}
	for (i = 0, j = n - 1; i < j; i++, j--)
		tmp = ta[1][i], ta[1][i] = ta[1][j], ta[1][j] = tmp;
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (i = 0; i < n; i++)
		idx[ta[0][i]] = ta[1][i];
	for (h = 0; h < q; h++) {
		if (ll_[0][h] > 0)
			append(ej, eo, ll_[0][h] - 1, h << 1 | 0);
		append(ej, eo, rr_[0][h] - 1, h << 1 | 1);
	}
	solve(n);
	for (h = 0; h < q; h++)
		ok[h] = kk[h] > 0;
	return ok;
}

Compilation message

werewolf.cpp: In function 'void append(int**, int*, int, int)':
werewolf.cpp:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
werewolf.cpp: In function 'void get_segment(int, int, int*, int*)':
werewolf.cpp:62:20: warning: unused variable 'o' [-Wunused-variable]
   62 |  int lower, upper, o;
      |                    ^
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:113:39: warning: unused variable 'h_' [-Wunused-variable]
  113 |  int m = xx.size(), q = ss.size(), h, h_, i, j, o, tmp;
      |                                       ^~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 5 ms 1228 KB Output is correct
11 Correct 6 ms 1228 KB Output is correct
12 Correct 13 ms 1228 KB Output is correct
13 Correct 5 ms 1228 KB Output is correct
14 Correct 6 ms 1228 KB Output is correct
15 Correct 7 ms 1356 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 59120 KB Output is correct
2 Correct 474 ms 58672 KB Output is correct
3 Correct 464 ms 67128 KB Output is correct
4 Correct 479 ms 67688 KB Output is correct
5 Correct 531 ms 67464 KB Output is correct
6 Correct 518 ms 67652 KB Output is correct
7 Correct 559 ms 67416 KB Output is correct
8 Correct 440 ms 67004 KB Output is correct
9 Correct 459 ms 67284 KB Output is correct
10 Correct 408 ms 67108 KB Output is correct
11 Correct 419 ms 67536 KB Output is correct
12 Correct 427 ms 67948 KB Output is correct
13 Correct 602 ms 67860 KB Output is correct
14 Correct 495 ms 67768 KB Output is correct
15 Correct 522 ms 67868 KB Output is correct
16 Correct 597 ms 67788 KB Output is correct
17 Correct 602 ms 67452 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 5 ms 1228 KB Output is correct
11 Correct 6 ms 1228 KB Output is correct
12 Correct 13 ms 1228 KB Output is correct
13 Correct 5 ms 1228 KB Output is correct
14 Correct 6 ms 1228 KB Output is correct
15 Correct 7 ms 1356 KB Output is correct
16 Correct 647 ms 59120 KB Output is correct
17 Correct 474 ms 58672 KB Output is correct
18 Correct 464 ms 67128 KB Output is correct
19 Correct 479 ms 67688 KB Output is correct
20 Correct 531 ms 67464 KB Output is correct
21 Correct 518 ms 67652 KB Output is correct
22 Correct 559 ms 67416 KB Output is correct
23 Correct 440 ms 67004 KB Output is correct
24 Correct 459 ms 67284 KB Output is correct
25 Correct 408 ms 67108 KB Output is correct
26 Correct 419 ms 67536 KB Output is correct
27 Correct 427 ms 67948 KB Output is correct
28 Correct 602 ms 67860 KB Output is correct
29 Correct 495 ms 67768 KB Output is correct
30 Correct 522 ms 67868 KB Output is correct
31 Correct 597 ms 67788 KB Output is correct
32 Correct 602 ms 67452 KB Output is correct
33 Correct 828 ms 67860 KB Output is correct
34 Correct 351 ms 41196 KB Output is correct
35 Correct 730 ms 68008 KB Output is correct
36 Correct 598 ms 67372 KB Output is correct
37 Correct 629 ms 67752 KB Output is correct
38 Correct 649 ms 67472 KB Output is correct
39 Correct 668 ms 68256 KB Output is correct
40 Correct 852 ms 75416 KB Output is correct
41 Correct 540 ms 68028 KB Output is correct
42 Correct 534 ms 67252 KB Output is correct
43 Correct 788 ms 70432 KB Output is correct
44 Correct 594 ms 68156 KB Output is correct
45 Correct 542 ms 68796 KB Output is correct
46 Correct 512 ms 68004 KB Output is correct
47 Correct 490 ms 67616 KB Output is correct
48 Correct 473 ms 67508 KB Output is correct
49 Correct 485 ms 68012 KB Output is correct
50 Correct 548 ms 67424 KB Output is correct
51 Correct 776 ms 76540 KB Output is correct
52 Correct 707 ms 76484 KB Output is correct