結果

問題 No.2301 Namorientation
コンテスト
ユーザー 👑 ygussany
提出日時 2023-04-29 20:28:19
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 489 ms / 3,000 ms
コード長 3,090 bytes
コンパイル時間 865 ms
コンパイル使用メモリ 32,240 KB
実行使用メモリ 43,648 KB
最終ジャッジ日時 2024-11-18 13:41:19
合計ジャッジ時間 13,417 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

#define CBM_n_MAX 500000
#define CBM_m_MAX 1000000

typedef struct Edge {
	struct Edge *next;
	int v;
} edge;

int augment_cardinality_bipartite_matching_HK(int n, char color[], edge *adj[], int mate[])
{
	int u, w, m, head, tail;
	static int depth[CBM_n_MAX + 1], indeg[CBM_n_MAX + 1], q[CBM_n_MAX + 1];
	static edge *aux[CBM_n_MAX + 1], *pred[CBM_n_MAX + 1], e[CBM_m_MAX * 2], *p;
	for (u = 1, tail = 0; u <= n; u++) {
		aux[u] = NULL;
		pred[u] = NULL;
		indeg[u] = 0;
		if (color[u] == 0 && mate[u] == 0) {
			depth[u] = 0;
			indeg[u] = 1;
			q[tail++] = u;
		} else depth[u] = -1;
	}
	for (head = 0, m = 0; head < tail; head++) {
		u = q[head];
		if (color[u] == 0) {
			for (p = adj[u]; p != NULL; p = p->next) {
				w = p->v;
				if (w == mate[u]) continue;
				if (depth[w] < 0) {
					depth[w] = depth[u] + 1;
					q[tail++] = w;
				}
				if (depth[w] == depth[u] + 1) {
					e[m].v = w;
					e[m].next = aux[u];
					aux[u] = &(e[m++]);
					e[m].v = u;
					e[m].next = pred[w];
					pred[w] = &(e[m++]);
					indeg[w]++;
				}
			}
		} else if (mate[u] != 0) {
			w = mate[u];
			if (depth[w] < 0) {
				depth[w] = depth[u] + 1;
				q[tail++] = w;
			}
			if (depth[w] == depth[u] + 1) {
				e[m].v = w;
				e[m].next = aux[u];
				aux[u] = &(e[m++]);
				e[m].v = u;
				e[m].next = pred[w];
				pred[w] = &(e[m++]);
				indeg[w]++;
			}
		}
	}
	
	int t, add = 0;
	for (t = 1; t <= n; t++) {
		if (color[t] == 0 || mate[t] != 0 || indeg[t] == 0) continue;
		else add++;
		
		for (u = t, tail = 0; 1; ) {
			indeg[u] = 0;
			q[tail++] = u;
			for (p = pred[u]; p != NULL; p = p->next) if (indeg[p->v] > 0) break;
			if (p == NULL) break;
			else u = p->v;
		}
		for (head = 0; head < tail; head += 2) {
			u = q[head];
			w = q[head+1];
			mate[u] = w;
			mate[w] = u;
		}
		
		for (head = 0; head < tail; head++) {
			u = q[head];
			for (p = aux[u]; p != NULL; p = p->next) {
				w = p->v;
				indeg[w]--;
				if (indeg[w] == 0) q[tail++] = w;
			}
		}
	}
	return add;
}

int cardinality_bipartite_matching_HK(int n, char color[], edge *adj[], int mate[])
{
	int ans = 0, add, u;
	for (u = 1; u <= n; u++) mate[u] = 0;
	do {
		add = augment_cardinality_bipartite_matching_HK(n, color, adj, mate);
		ans += add;
	} while (add != 0);
	return ans;
}



int main()
{
	int i, N, u, w, A[200001], B[200001];
	edge *adj[400001] = {}, e[800001], *p;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d %d", &u, &w);
		e[i*4].v = N + i + 1;
		e[i*4].next = adj[u];
		adj[u] = &(e[i*4]);
		e[i*4+1].v = u;
		e[i*4+1].next = adj[N+i+1];
		adj[N+i+1] = &(e[i*4+1]);
		e[i*4+2].v = N + i + 1;
		e[i*4+2].next = adj[w];
		adj[w] = &(e[i*4+2]);
		e[i*4+3].v = w;
		e[i*4+3].next = adj[N+i+1];
		adj[N+i+1] = &(e[i*4+3]);
		A[i] = u;
		B[i] = w;
	}
	
	char color[400001];
	int mate[400001];
	for (u = 1; u <= N; u++) color[u] = 0;
	for (u = N + 1; u <= N * 2; u++) color[u] = 1;
	cardinality_bipartite_matching_HK(N * 2, color, adj, mate);
	for (i = 0; i < N; i++) {
		if (mate[N+i+1] == A[i]) printf("->\n");
		else printf("<-\n");
	}
	fflush(stdout);
	return 0;
}
0