結果
問題 | No.317 辺の追加 |
ユーザー |
![]() |
提出日時 | 2025-01-18 18:16:51 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,032 bytes |
コンパイル時間 | 532 ms |
コンパイル使用メモリ | 59,240 KB |
実行使用メモリ | 13,952 KB |
最終ジャッジ日時 | 2025-01-18 18:16:59 |
合計ジャッジ時間 | 7,689 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 WA * 25 |
ソースコード
#include <iostream>using namespace std;typedef long long ll;ll n, m, e[400002], h[100002], ne[400002], idx, dp[100002], cnt[100002], az[1002], l, ans;bool f[100002];void add(ll x, ll y) {e[++ idx] = y, ne[idx] = h[x], h[x] = idx;}void dfs(ll x) {ans ++;f[x] = 1;for (ll i = h[x]; i; i = ne[i]) {ll y = e[i];if (! f[y]) dfs(y);}}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for (ll x, y; m --; ) cin >> x >> y, add(x, y), add(y, x);for (ll i = 1; i <= n; i ++ ) if (! f[i]) ans = 0, dfs(i), cnt[ans] ++;for (ll i = 1; i <= n; i ++ ) {if (! cnt[i]) continue;ll p = 1;while (p <= cnt[i]) {if (cnt[i] % (p << 1)) az[++ l] = p * i, cnt[i] -= p;p <<= 1;}if (cnt[i]) az[++ l] = cnt[i] * i;}for (ll i = 1; i <= n; i ++ ) dp[i] = 0x3f3f3f3f3f3f3f3f;dp[0] = 0;for (ll i = 1; i <= l; i ++ ) for (ll j = n; j >= az[i]; j -- ) dp[j] = min(dp[j], dp[j - az[i]] + 1);for (ll i = 1; i <= n; i ++ ) cout << (dp[i] >= n ? -1ll : dp[i] - 1) << endl;}