結果

問題 No.468 役に立つ競技プログラミング実践編
コンテスト
ユーザー bal4u
提出日時 2019-08-29 14:17:40
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 81 ms / 2,000 ms
コード長 2,367 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 32,256 KB
実行使用メモリ 24,212 KB
最終ジャッジ日時 2024-11-17 16:50:13
合計ジャッジ時間 3,659 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 31
other AC * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:9:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
    9 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:15:24: note: in expansion of macro 'gc'
   15 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff # 

// yukicoder: 468 役に立つ競技プログラミング実践編
// 2019.8.29 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

#define INF
#define MAX 100005
int N;
int hi[MAX], *to[MAX], *C[MAX];
int rhi[MAX], *rto[MAX], *rC[MAX];
int start[MAX], last[MAX];

inline static void chmax(int *a, int b) { if (*a < b) *a = b; }
inline static void chmin(int *a, int b) { if (*a > b) *a = b; }

// トポロジーソート 独立したモジュール
void topoSort(int V) {
	int i, j, k;
	static int q[MAX], top, end;
	static int count[MAX];

	for (i = 0; i < V; i++) for (j = 0; j < hi[i]; j++) count[to[i][j]]++;
	top = end = 0;
	for (i = 0; i < V; i++) if (!count[i]) q[end++] = i;
	while (top < end) {
		i = q[top++];
		for (j = 0; j < hi[i]; j++) {
			k = to[i][j];
/**/		chmax(&start[k], start[i] + C[i][j]);
			if (--count[k] == 0) q[end++] = k;
		}
	}
}

void rtopoSort(int V) {
	int i, j, k;
	static int q[MAX], top, end;
	static int count[MAX];

	for (i = 0; i < V; i++) for (j = 0; j < rhi[i]; j++) count[rto[i][j]]++;
	top = end = 0;
	for (i = 0; i < V; i++) if (!count[i]) q[end++] = i;
	while (top < end) {
		i = q[top++];
		for (j = 0; j < rhi[i]; j++) {
			k = rto[i][j];
/**/		chmin(&last[k], last[i] - rC[i][j]);
			if (--count[k] == 0) q[end++] = k;
		}
	}
}

int main()
{
	int i, k, a, b, c, M;
	int *memo, sz;
	
	N = in(), M = in();
	memo = malloc(sizeof(int)*M*3);
	sz = 0; for (i = 0; i < M; i++) {
		memo[sz++] = a = in(), memo[sz++] = b = in(), memo[sz++] = in();
		hi[a]++, rhi[b]++;
	}
	for (i = 0; i < N; i++) {
		if (hi[i]) {
			to[i] = malloc(hi[i]*sizeof(int)), C[i] = malloc(hi[i]*sizeof(int));
		}
		if (rhi[i]) {
			rto[i] = malloc(rhi[i]*sizeof(int)), rC[i] = malloc(rhi[i]*sizeof(int));
		}
	}
	memset(hi, 0, sizeof(hi)), 	memset(rhi, 0, sizeof(rhi));
	
	i = 0; while (i < sz) {
		a = memo[i++], b = memo[i++], c = memo[i++];
		k =  hi[a]++,  to[a][k] = b,  C[a][k] = c;
		k = rhi[b]++, rto[b][k] = a, rC[b][k] = c;
	}
	
	topoSort(N);
	for (i = 0; i < N; i++) last[i] = start[N-1];
	rtopoSort(N);

	k = 0; for (i = 0; i < N; i++) if (start[i] != last[i]) k++;
	printf("%d %d/%d\n", start[N-1], k, N);
	return 0;
}
0