oj.uz

답안 #531897

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
531897 2022-03-01T20:47:28 Z rainboy 동기화 (JOI13_synchronization) C
20 / 100
 8000 ms 208220 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	100000
#define M	200000
#define LG	18	/* LG = ceil(log2(M)) */
#define N_	(1 + M * (LG * 2 + 3))

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ij[N - 1];
int *eh[N], eo[N], *eg[N - 1], eo_[N - 1], n, k;

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 delete(int i, int h) {
	int o;

	for (o = eo[i]; o--; )
		if (eh[i][o] == h) {
			eo[i]--;
			while (o < eo[i])
				eh[i][o] = eh[i][o + 1], o++;
			return;
		}
}

int vv[N_], ll[N_], rr[N_], _, __;

int node(int v, int l, int r) {
	_++;
	vv[_] = v;
	if (l == 0 && r == 0)
		ll[_] = rr[_] = _;
	else
		ll[_] = l, rr[_] = r;
	return _;
}

int build(int l, int r) {
	if (r - l == 1)
		return node(l, 0, 0);
	else {
		int m = (l + r) / 2;

		return node(0, build(l, m), build(m, r));
	}
}

int update(int t, int l, int r, int ql, int qr, int v) {
	int m;

	if (qr <= l || r <= ql)
		return t;
	if (ql <= l && r <= qr)
		return node(v, 0, 0);
	m = (l + r) / 2;
	return node(0, update(ll[t], l, m, ql, qr, v), update(rr[t], m, r, ql, qr, v));
}

int query(int t, int l, int r, int i) {
	int m;

	if (r - l == 1)
		return vv[t];
	m = (l + r) / 2;
	return i < m ? query(ll[t], l, m, i) : query(rr[t], m, r, i);
}

int sz[N], c;

void dfs1(int p, int i, int n) {
	int o, centroid;

	sz[i] = 1, centroid = 1;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		if (j != p) {
			dfs1(i, j, n);
			sz[i] += sz[j];
			if (sz[j] * 2 > n)
				centroid = 0;
		}
	}
	if ((n - sz[i]) * 2 > n)
		centroid = 0;
	if (centroid)
		c = i;
}

int xx[N], yy[N], qu[N], cnt;

void process(int h, int tx, int ty, int *tx_, int *ty_) {
	int o;

	for (o = 0; o <= eo_[h]; o += 2) {
		int l = o == 0 ? -1 : eg[h][o - 1];
		int r = o == eo_[h] ? k : eg[h][o];

		if (l + 1 < r) {
			tx = update(tx, 0, k, l + 1, r, r == k ? k : query(tx, 0, k, r));
			ty = update(ty, 0, k, l + 1, r, l == -1 ? -1 : query(ty, 0, k, l));
		}
	}
	*tx_ = tx, *ty_ = ty;
}

void dfs2(int p, int i, int tx, int ty) {
	int o;

	qu[cnt++] = i;
	xx[i] = query(tx, 0, k, 0), yy[i] = query(ty, 0, k, k - 1);
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		if (j != p) {
			int tx_, ty_;

			process(h, tx, ty, &tx_, &ty_);
			dfs2(i, j, tx_, ty_);
		}
	}
}

void dfs3(int p, int i) {
	int o;

	qu[cnt++] = i;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		if (j != p)
			dfs3(i, j);
	}
}

int zz[N * 2];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (zz[hh[j]] == zz[h])
				j++;
			else if (zz[hh[j]] < zz[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int kk[N];

void solve(int sgn) {
	static int hh[N * 2];
	int h, k;

	for (h = 0; h < cnt; h++) {
		zz[h << 1 | 0] = xx[qu[h]] * 2 + 0;
		zz[h << 1 | 1] = yy[qu[h]] * 2 + 1;
	}
	for (h = 0; h < cnt * 2; h++)
		hh[h] = h;
	sort(hh, 0, cnt * 2);
	k = 0;
	for (h = 0; h < cnt * 2; h++)
		if ((hh[h] & 1) == 0)
			k++;
		else
			kk[qu[hh[h] >> 1]] += k * sgn;
}

int t;

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

	dfs1(-1, i, n), i = c;
	_ = __;
	cnt = 0, dfs2(-1, i, t, t);
	solve(1);
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		cnt = 0, dfs3(i, j);
		solve(-1);
	}
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		delete(j, h);
		cd(j, sz[j] < sz[i] ? sz[j] : n - sz[i]);
	}
}

int main() {
	int q, g, h, i, j;

	scanf("%d%d%d", &n, &k, &q);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		ij[h] = i ^ j;
		append(eh, eo, i, h), append(eh, eo, j, h);
	}
	for (h = 0; h < n - 1; h++)
		eg[h] = (int *) malloc(2 * sizeof *eg[h]);
	for (g = 0; g < k; g++) {
		scanf("%d", &h), h--;
		append(eg, eo_, h, g);
	}
	t = build(0, k), __ = _;
	cd(0, n);
	while (q--) {
		scanf("%d", &i), i--;
		printf("%d\n", kk[i]);
	}
	return 0;
}

Compilation message

synchronization.c: In function 'append':
synchronization.c:21:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
synchronization.c: In function 'main':
synchronization.c:216:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |  scanf("%d%d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.c:220:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
synchronization.c:227:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  227 |   scanf("%d", &h), h--;
      |   ^~~~~~~~~~~~~~~
synchronization.c:233:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |   scanf("%d", &i), i--;
      |   ^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 1196 KB Output is correct
7 Correct 81 ms 11340 KB Output is correct
8 Correct 79 ms 11332 KB Output is correct
9 Correct 92 ms 11428 KB Output is correct
10 Runtime error 303 ms 208220 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 626 ms 104436 KB Output is correct
2 Correct 603 ms 102940 KB Output is correct
3 Correct 899 ms 80380 KB Output is correct
4 Correct 889 ms 80376 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 8 ms 1228 KB Output is correct
7 Correct 118 ms 12156 KB Output is correct
8 Execution timed out 8100 ms 110624 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8038 ms 110900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 5 ms 1132 KB Output is correct
6 Correct 83 ms 11344 KB Output is correct
7 Execution timed out 8023 ms 103248 KB Time limit exceeded
8 Halted 0 ms 0 KB -