結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2025-01-19 12:05:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,014 bytes |
コンパイル時間 | 4,960 ms |
コンパイル使用メモリ | 273,524 KB |
実行使用メモリ | 22,924 KB |
最終ジャッジ日時 | 2025-01-19 12:06:06 |
合計ジャッジ時間 | 26,098 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 TLE * 5 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:24:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 24 | scanf("%d %d", &u, &v); | ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; int n, m, e, h[1145141], ne[1145141], t[1145141], u, v, b[1145141], is[1145141], cnt, f[2][114514]; int ct (int x, int y) { e++; ne[e] = h[x]; h[x] = e; t[e] = y; return 0; } int dfs(int x, int y) { is[x] = 1; b[y]++; for (int i = h[x]; i; i = ne[i]) { if (!is[t[i]]) { dfs(t[i], y); } } return 0; } int main () { cin >> n >> m; for (int i = 1; i <= m; i++) { scanf("%d %d", &u, &v); ct(u, v); ct(v, u); } for (int i = 1; i <= n; i++) { if(!is[i]) { dfs(i, ++cnt); } } for (int i = 0; i <= 1; i++) { for (int j = 1; j <= n; j++) { f[i][j] = 11451419; } } f[0][0] = 0; for (int i = 1; i <= cnt; i++) { for (int j = n; j >= b[i]; j--) { f[i & 1][j] = min(f[(i - 1) & 1][j - b[i]] + 1, f[(i - 1) & 1][j]); } for (int j = b[i] - 1; j; j--) f[i & 1][j] = f[(i - 1) & 1][j]; f[i & 1][b[i]] = 0; } for (int i = 1; i <= n; i++) { if (f[cnt & 1][i] >= 11451419) cout << "-1\n"; else cout << f[cnt & 1][i] << "\n"; } }