結果

問題 No.19 ステージの選択
ユーザー bal4u
提出日時 2019-04-11 07:44:28
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 2,251 bytes
コンパイル時間 375 ms
コンパイル使用メモリ 31,744 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 01:49:40
合計ジャッジ時間 1,361 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:17:24: note: in expansion of macro 'gc'
   17 |         int n = 0, c = gc();
      |                        ^~
main.c: In function 'main':
main.c:10:15: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
   10 | #define pc(c) putchar_unlocked(c)
      |               ^~~~~~~~~~~~~~~~
main.c:125:9: note: in expansion of macro 'pc'
  125 |         pc(ans & 1? '5': '0');
      |         ^~
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 1
#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][2];
int grp[105][105], len[105];

int calc(int gid)
{
	int i, s, min, ans;

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

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

	V = in();
	for (i = 0; i < V; i++) {
		L[i][1] = in(), L[i][0] = L[i][1] << 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) ans += calc(i);
		else {
			s = grp[i][0];
			ans += L[s][r_hi[s] > 0];
		}
	}
	printf("%d.", ans >> 1);
	pc(ans & 1? '5': '0');
	pc('\n');
	return 0;
}
0