oj.uz

답안 #435648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435648 2021-06-23T14:10:45 Z rainboy 늑대인간 (IOI18_werewolf) C++11
15 / 100
 4000 ms 57468 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[N], tb[N], qu[2][N], time;

void dfs(int i) {
	int o;

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

		dfs(j);
	}
	tb[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[i], *r = lower == -1 ? ta[i] + 1 : tb[fj[i][lower]];
}

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

	for (t = 0; t < 2; t++) {
		int tmp;

		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; i < n; i++)
		qu[1][i] = n - 1 - qu[1][i];
	for (h = 0; h < q; h++) {
		for (h_ = ll_[0][h]; h_ < rr_[0][h]; h_++)
			used[qu[0][h_]] = 1;
		for (h_ = ll_[1][h]; h_ < rr_[1][h]; h_++)
			if (used[qu[1][h_]]) {
				ok[h] = 1;
				break;
			}
		for (h_ = ll_[0][h]; h_ < rr_[0][h]; h_++)
			used[qu[0][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;
      |                    ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 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 32 ms 1120 KB Output is correct
11 Correct 22 ms 1220 KB Output is correct
12 Correct 8 ms 1096 KB Output is correct
13 Correct 21 ms 1228 KB Output is correct
14 Correct 11 ms 1224 KB Output is correct
15 Correct 26 ms 1344 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 670 ms 50676 KB Output is correct
2 Execution timed out 4054 ms 57468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 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 32 ms 1120 KB Output is correct
11 Correct 22 ms 1220 KB Output is correct
12 Correct 8 ms 1096 KB Output is correct
13 Correct 21 ms 1228 KB Output is correct
14 Correct 11 ms 1224 KB Output is correct
15 Correct 26 ms 1344 KB Output is correct
16 Correct 670 ms 50676 KB Output is correct
17 Execution timed out 4054 ms 57468 KB Time limit exceeded
18 Halted 0 ms 0 KB -