結果

問題 No.468 役に立つ競技プログラミング実践編
ユーザー bal4ubal4u
提出日時 2019-08-29 14:17:40
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 2,367 bytes
コンパイル時間 477 ms
コンパイル使用メモリ 30,916 KB
実行使用メモリ 24,216 KB
最終ジャッジ日時 2023-08-11 04:01:01
合計ジャッジ時間 5,268 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,876 KB
testcase_01 AC 2 ms
5,900 KB
testcase_02 AC 1 ms
5,948 KB
testcase_03 AC 2 ms
5,920 KB
testcase_04 AC 1 ms
5,868 KB
testcase_05 AC 2 ms
5,832 KB
testcase_06 AC 2 ms
5,916 KB
testcase_07 AC 1 ms
5,824 KB
testcase_08 AC 2 ms
5,836 KB
testcase_09 AC 1 ms
5,960 KB
testcase_10 AC 2 ms
5,932 KB
testcase_11 AC 2 ms
5,824 KB
testcase_12 AC 1 ms
5,928 KB
testcase_13 AC 1 ms
5,924 KB
testcase_14 AC 3 ms
6,068 KB
testcase_15 AC 2 ms
5,996 KB
testcase_16 AC 2 ms
6,112 KB
testcase_17 AC 2 ms
5,996 KB
testcase_18 AC 2 ms
6,012 KB
testcase_19 AC 2 ms
6,116 KB
testcase_20 AC 2 ms
6,056 KB
testcase_21 AC 2 ms
6,128 KB
testcase_22 AC 2 ms
6,008 KB
testcase_23 AC 2 ms
6,064 KB
testcase_24 AC 91 ms
24,152 KB
testcase_25 AC 90 ms
24,160 KB
testcase_26 AC 93 ms
24,148 KB
testcase_27 AC 88 ms
24,096 KB
testcase_28 AC 89 ms
24,152 KB
testcase_29 AC 89 ms
24,092 KB
testcase_30 AC 91 ms
24,112 KB
testcase_31 AC 89 ms
24,216 KB
testcase_32 AC 91 ms
24,084 KB
testcase_33 AC 91 ms
24,088 KB
testcase_34 AC 38 ms
21,620 KB
testcase_35 AC 2 ms
6,000 KB
testcase_36 AC 1 ms
5,956 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: 関数 ‘in’ 内:
main.c:9:14: 警告: 関数 ‘getchar_unlocked’ の暗黙的な宣言です [-Wimplicit-function-declaration]
    9 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:15:24: 備考: 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