結果

問題 No.19 ステージの選択
ユーザー bal4u
提出日時 2019-04-11 06:59:18
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,303 bytes
コンパイル時間 387 ms
コンパイル使用メモリ 31,488 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-18 00:40:33
合計ジャッジ時間 1,403 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'scc':
main.c:74:9: warning: 'memset' specified size between 18446744071562067968 and 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   74 |         memset(used, 0, V);
      |         ^~~~~~~~~~~~~~~~~~
main.c:30:6: note: destination object allocated here
   30 | char used[MAX_V];
      |      ^~~~

ソースコード

diff # 

// yukicoder: No.19 ステージの選択
// 2019.4.11 bal4u

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

//// 高速入力
#if 0
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif
int in()    // 非負整数の入力
{
	int n = 0, c = gc();
//	while (isspace(c)) c = gc();
	do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}


////　強連結成分への分解
#define MAX_V 105
int  V;    // 頂点数
int  to[MAX_V][MAX_V], hi[MAX_V];
int  r_to[MAX_V][MAX_V], r_hi[MAX_V];
int  vs[MAX_V], vsz;
char used[MAX_V];
int  cmp[MAX_V];    // 属する強連結成分のトポロジカル順序

void add_edge(int _from, int _to)
{
	to[_from][hi[_from]++] = _to;
	r_to[_to][r_hi[_to]++] = _from;
}

void dfs(int v)
{
	int i;
	used[v] = 1;
	for (i = 0; i < hi[v]; i++) {
		if (!used[to[v][i]]) dfs(to[v][i]);
	}
	vs[vsz++] = v;
}

void rdfs(int v, int k)
{
	int i;
	used[v] = 1;
	cmp[v] = k;
	for (i = 0; i < r_hi[v]; i++) {
		if (!used[r_to[v][i]]) rdfs(r_to[v][i], k);
	}
}

#if 0
void init(int n)
{
	V = n;
	memset(lim, 0, V << 2), memset(hi, 0, V << 2);
	memset(r_lim, 0, V << 2), memset(r_hi, 0, V << 2);
}
#endif

int scc()
{
	int v, i, k;
	memset(used, 0, V);
	vsz = 0;
	for (v = 0; v < V; v++) if (!used[v]) dfs(v);
	memset(used, 0, V);
	k = 0;
	for (i = vsz - 1; i >= 0; i--) {
		if (!used[vs[i]]) rdfs(vs[i], k++);
	}
	return k;		// 得られた強連結成分の数
}

#define INF 0x7fffffff
int L[105];
int grp[105][105], len[105];

int calc(int gid)
{
	int i, j, s, t, min;

	min = INF, s = 0;
	for (i = 0; i < len[gid]; i++) {
		t = grp[gid][i], s = L[t];
		for (j = 1; j < len[gid]; j++) {
			t = to[t][0];
			s += L[t] >> 1;
		}
		if (s < min) min = s;
	}
	return min;
}

int main()
{
	int i, j, n, s, ans;

	V = in();
	for (i = 0; i < V; i++) {
		L[i] = in() << 1, j = in() - 1;
		if (i != j) add_edge(j, i);
	}
	n = scc();   // 各強連結成分を求める

	for (i = 0; i < V; i++) {
		s = cmp[i];
		grp[s][len[s]++] = i;
	}

	ans = 0;
	for (i = 0; i < n; i++) { // 各強連結成分について
		if (len[i] == 1) {
			s = grp[i][0];
			if (r_hi[s] > 0) ans += L[s] >> 1;
			else ans += L[s];
		}
		else ans += calc(i);
	}
	printf("%d.", ans >> 1);
	pc(ans & 1? '5': '0');
	pc('\n');
	return 0;
}
0