제출 #544754

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544754		rainboy	Joker (BOI20_joker)	C11	100 / 100	617 ms	22700 KiB

Joker

/* https://codeforces.com/blog/entry/80490?#comment-667089 (Benq) */
#include <stdio.h>
#include <string.h>

#define N	200000
#define M	200000
#define N_	(M * 2 + N)
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int ds[N * 2];

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

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

int tt[1 + N_][2], pp[1 + N_], mn[1 + N_], n, m; char odd[1 + N_], rev[1 + N_];

int dir(int u) {
	return tt[pp[u]][0] == u ? 0 : 1;
}

int is_root(int u) {
	return tt[pp[u]][0] != u && tt[pp[u]][1] != u;
}

void put(int u) {
	if (u) {
		int tmp;

		tmp = tt[u][0], tt[u][0] = tt[u][1], tt[u][1] = tmp;
		rev[u] ^= 1;
	}
}

void pus(int u) {
	if (rev[u])
		put(tt[u][0]), put(tt[u][1]), rev[u] = 0;
}

void pul(int u) {
	if (!rev[u]) {
		int l = tt[u][0], r = tt[u][1];

		mn[u] = min(u, min(mn[l], mn[r]));
		odd[u] = (u <= m * 2) ^ odd[l] ^ odd[r];
	}
}

void attach(int p, int u, int d) {
	if (p)
		tt[p][d] = u, pul(p);
	if (u)
		pp[u] = p;
}

void rotate(int u) {
	int v = pp[u], w = pp[v], du = dir(u), dv = dir(v);

	if (is_root(v))
		pp[u] = w;
	else
		attach(w, u, dv);
	attach(v, tt[u][du ^ 1], du);
	attach(u, v, du ^ 1);
}

void splay(int u) {
	while (!is_root(u)) {
		int v = pp[u], w = pp[v];

		pus(w), pus(v), pus(u);
		if (!is_root(v))
			rotate(dir(u) == dir(v) ? v : u);
		rotate(u);
	}
	pus(u);
}

int first(int u) {
	pus(u);
	while (tt[u][0])
		pus(u = tt[u][0]);
	splay(u);
	return u;
}

int find_min(int u) {
	pus(u);
	while (mn[u] != u)
		pus(u = tt[u][mn[tt[u][0]] == mn[u] ? 0 : 1]);
	splay(u);
	return u;
}

void expose(int u) {
	int v, w;

	for (w = 0, v = u; v; w = v, v = pp[v]) {
		splay(v);
		attach(v, w, 1);
	}
	splay(u);
}

void make_root(int u) {
	expose(u), put(u);
}

void link(int u, int v) {
	make_root(u), expose(v);
	attach(v, u, 1);
}

void cut(int u, int v) {
	make_root(u), expose(v);
	pp[tt[v][0]] = 0, attach(v, 0, 0);
}

int uu[1 + M * 2], vv[1 + M * 2]; char used[1 + M * 2];

void cut_(int h);

int cnt;

int link_(int h) {
	int u = uu[h], v = vv[h];

	make_root(u);
	expose(v);
	if (first(v) == u) {
		if (!odd[u])
			return 0;
		cut_(find_min(u));
	}
	link(u, h), link(v, h);
	used[h] = 1;
	return 1;
}

void cut_(int h) {
	if (used[h]) {
		int u = uu[h], v = vv[h];

		cut(u, h), cut(v, h);
		used[h] = 0;
	}
}

int main() {
	static int rr[1 + M];
	int q, h, l, r, u, v;

	scanf("%d%d%d", &n, &m, &q);
	for (h = 1; h <= m; h++) {
		scanf("%d%d", &u, &v);
		uu[h] = m * 2 + u, vv[h] = m * 2 + v;
		uu[m + h] = m * 2 + u, vv[m + h] = m * 2 + v;
	}
	memset(ds, -1, n * 2 * sizeof *ds);
	for (r = m; r > 0; r--) {
		u = uu[r] - m * 2 - 1, v = vv[r] - m * 2 - 1;
		if (find(u << 1 | 0) == find(v << 1 | 0))
			break;
		join(u << 1 | 0, v << 1 | 1), join(u << 1 | 1, v << 1 | 0);
	}
	if (r++ > 0) {
		mn[0] = INF;
		for (u = 1; u <= m * 2; u++)
			odd[u] = 1;
		for (h = r; h <= m; h++)
			link_(h);
		for (l = 1; l <= m; l++) {
			u = uu[l], v = vv[l];
			rr[l] = r - 1;
			while (r <= m + 1 && !link_(m + l)) {
				if (r == m + 1) {
					while (++l <= m)
						rr[l] = m + 1;
					break;
				}
				cut_(r++);
			}
		}
	}
	while (q--) {
		scanf("%d%d", &l, &r);
		printf(rr[l] <= r ? "NO\n" : "YES\n");
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Joker.c: In function 'main':
Joker.c:169:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.c:171:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |   scanf("%d%d", &u, &v);
      |   ^~~~~~~~~~~~~~~~~~~~~
Joker.c:202:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |   scanf("%d%d", &l, &r);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29