結果

問題 No.317 辺の追加
ユーザー vjudge1
提出日時 2025-01-19 15:25:09
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 58 ms / 2,000 ms
コード長 1,093 bytes
コンパイル時間 939 ms
コンパイル使用メモリ 62,192 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-19 15:25:15
合計ジャッジ時間 4,196 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:29:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   29 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:33:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |     scanf("%d %d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <algorithm>
#include <cstdio>
#include <numeric>

constexpr int N = 1e5 + 5, Inf = 0x3f3f3f3f;

int n, m, f[N], s[N], cnt[N], dp[N];

void init(int n) {
  std::iota(f + 1, f + n + 1, 1);
  std::fill(s + 1, s + n + 1, 1);
}

int find(int u) { return u == f[u] ? u : f[u] = find(f[u]); }

void merge(int u, int v) {
  int fu = find(u), fv = find(v);
  if (fu == fv) return;
  if (s[fu] < s[fv]) std::swap(fu, fv);
  f[fv] = fu;
  s[fu] += s[fv];
}

void update(int v, int w) {
  for (int vv = n; vv >= v; --vv) dp[vv] = std::min(dp[vv], dp[vv - v] + w);
}

int main() {
  scanf("%d %d", &n, &m);
  init(n);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    merge(u, v);
  }
  for (int i = 1; i <= n; ++i) {
    dp[i] = Inf;
    if (i == f[i]) ++cnt[s[i]];
  }
  for (int i = 1; i <= n; ++i)
    if (cnt[i]) {
      int b = 1;
      while (cnt[i] > b) {
        update(i * b, b);
        cnt[i] -= b;
        b <<= 1;
      }
      if (cnt[i]) update(i * cnt[i], cnt[i]);
    }
  for (int i = 1; i <= n; ++i) printf("%d\n", (dp[i] == Inf ? 0 : dp[i]) - 1);
}
0