結果
問題 | No.317 辺の追加 |
ユーザー |
|
提出日時 | 2017-11-18 14:45:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 180 ms / 2,000 ms |
コード長 | 3,148 bytes |
コンパイル時間 | 1,942 ms |
コンパイル使用メモリ | 185,592 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-25 11:34:22 |
合計ジャッジ時間 | 8,913 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>#define show(x) cerr << #x << " = " << x << endlusing namespace std;using ll = long long;using pii = pair<int, int>;using vi = vector<int>;template <typename T>ostream& operator<<(ostream& os, const vector<T>& v){os << "sz=" << v.size() << "\n[";for (const auto& p : v) {os << p << ",";}os << "]\n";return os;}template <typename S, typename T>ostream& operator<<(ostream& os, const pair<S, T>& p){os << "(" << p.first << "," << p.second<< ")";return os;}constexpr ll MOD = 1e9 + 7;template <typename T>constexpr T INF = numeric_limits<T>::max() / 100;class DisjointSets{public:DisjointSets(const int v){m_parent.resize(v);m_rank.resize(v);m_size.resize(v);for (int i = 0; i < v; i++) {m_parent[i] = i;m_rank[i] = 0;m_size[i] = 1;}}bool same(const int a, const int b){return find(a) == find(b);}int find(const int a){if (m_parent[a] == a) {return a;} else {return m_parent[a] = find(m_parent[a]);}}void unite(const int a_, const int b_){const int a = find(a_);const int b = find(b_);if (a == b) {return;}if (m_rank[a] > m_rank[b]) {m_parent[b] = a;m_size[a] += m_size[b];} else {m_parent[a] = b;m_size[b] += m_size[a];}if (m_rank[a] == m_rank[b]) {m_rank[b]++;}}int getSize(const int a){return m_size[m_parent[a]];}private:vector<int> m_parent;vector<int> m_rank;vector<int> m_size;};int main(){cin.tie(0);ios::sync_with_stdio(false);int N, M;cin >> N >> M;DisjointSets uf(N);for (int i = 0; i < M; i++) {int u, v;cin >> u >> v;u--, v--;uf.unite(u, v);}vector<int> node(N, 0);for (int i = 0; i < N; i++) {node[uf.find(i)]++;}vector<int> num;for (int i = 0; i < N; i++) {if (node[i] > 0) {num.push_back(node[i]);}}sort(num.begin(), num.end());map<int, int> mp;for (int i = 0; i < num.size(); i++) {mp[num[i]]++;}auto a = num;a.erase(unique(a.begin(), a.end()), a.end());const int size = a.size();vector<int> m(size, 0);for (int i = 0; i < size; i++) {m[i] = mp[a[i]];}vector<int> dp(N + 1, INF<int>);dp[0] = -1;for (int i = 0; i < size; i++) {int num = m[i];for (int k = 1; num > 0; k <<= 1) {const int mul = min(k, num);for (int j = N; j >= a[i] * mul; j--) {dp[j] = min(dp[j], dp[j - a[i] * mul] + mul);}num -= mul;}}for (int i = 1; i <= N; i++) {if (dp[i] != INF<int>) {cout << dp[i] << endl;} else {cout << -1 << endl;}}return 0;}