oj.uz

Submission #531898

# Submission time Handle Problem Language Result Execution time Memory
531898 2022-03-01T20:50:21 Z rainboy Synchronization (JOI13_synchronization) C
100 / 100
 2054 ms 140228 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	100000
#define M	200000
#define LG	18	/* LG = ceil(log2(M)) */
#define N_	(1 + M * 2 * (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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 7 ms 1100 KB Output is correct
7 Correct 91 ms 11284 KB Output is correct
8 Correct 83 ms 11292 KB Output is correct
9 Correct 86 ms 11300 KB Output is correct
10 Correct 1528 ms 132096 KB Output is correct
11 Correct 1517 ms 132412 KB Output is correct
12 Correct 1993 ms 140124 KB Output is correct
13 Correct 283 ms 132660 KB Output is correct
14 Correct 932 ms 72672 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 103668 KB Output is correct
2 Correct 648 ms 102264 KB Output is correct
3 Correct 973 ms 79860 KB Output is correct
4 Correct 938 ms 79824 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 11 ms 1228 KB Output is correct
7 Correct 136 ms 11920 KB Output is correct
8 Correct 1987 ms 139844 KB Output is correct
9 Correct 1963 ms 140212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1973 ms 139724 KB Output is correct
2 Correct 973 ms 80332 KB Output is correct
3 Correct 966 ms 80896 KB Output is correct
4 Correct 971 ms 80944 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 6 ms 1200 KB Output is correct
6 Correct 87 ms 11148 KB Output is correct
7 Correct 1543 ms 132212 KB Output is correct
8 Correct 2054 ms 140228 KB Output is correct
9 Correct 313 ms 133224 KB Output is correct
10 Correct 1034 ms 73304 KB Output is correct
11 Correct 677 ms 104732 KB Output is correct
12 Correct 715 ms 104696 KB Output is correct
13 Correct 954 ms 80956 KB Output is correct