結果
問題 | No.317 辺の追加 |
ユーザー | pekempey |
提出日時 | 2015-12-10 17:27:06 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 623 ms / 2,000 ms |
コード長 | 2,470 bytes |
コンパイル時間 | 1,501 ms |
コンパイル使用メモリ | 162,016 KB |
実行使用メモリ | 14,568 KB |
最終ジャッジ日時 | 2023-10-13 10:34:25 |
合計ジャッジ時間 | 12,015 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
9,120 KB |
testcase_01 | AC | 6 ms
9,088 KB |
testcase_02 | AC | 46 ms
13,208 KB |
testcase_03 | AC | 46 ms
12,648 KB |
testcase_04 | AC | 119 ms
13,908 KB |
testcase_05 | AC | 43 ms
11,444 KB |
testcase_06 | AC | 54 ms
12,476 KB |
testcase_07 | AC | 21 ms
10,208 KB |
testcase_08 | AC | 457 ms
11,536 KB |
testcase_09 | AC | 58 ms
14,432 KB |
testcase_10 | AC | 62 ms
14,568 KB |
testcase_11 | AC | 97 ms
13,532 KB |
testcase_12 | AC | 62 ms
14,500 KB |
testcase_13 | AC | 170 ms
12,856 KB |
testcase_14 | AC | 57 ms
14,436 KB |
testcase_15 | AC | 59 ms
14,436 KB |
testcase_16 | AC | 98 ms
14,404 KB |
testcase_17 | AC | 57 ms
14,456 KB |
testcase_18 | AC | 63 ms
14,436 KB |
testcase_19 | AC | 62 ms
14,496 KB |
testcase_20 | AC | 161 ms
14,384 KB |
testcase_21 | AC | 27 ms
11,592 KB |
testcase_22 | AC | 18 ms
9,920 KB |
testcase_23 | AC | 19 ms
10,424 KB |
testcase_24 | AC | 39 ms
13,576 KB |
testcase_25 | AC | 28 ms
12,484 KB |
testcase_26 | AC | 31 ms
12,848 KB |
testcase_27 | AC | 27 ms
12,116 KB |
testcase_28 | AC | 18 ms
10,164 KB |
testcase_29 | AC | 9 ms
9,372 KB |
testcase_30 | AC | 531 ms
9,884 KB |
testcase_31 | AC | 606 ms
9,836 KB |
testcase_32 | AC | 609 ms
9,896 KB |
testcase_33 | AC | 606 ms
9,880 KB |
testcase_34 | AC | 595 ms
9,852 KB |
testcase_35 | AC | 609 ms
9,852 KB |
testcase_36 | AC | 606 ms
9,960 KB |
testcase_37 | AC | 623 ms
9,912 KB |
testcase_38 | AC | 532 ms
9,840 KB |
testcase_39 | AC | 611 ms
9,900 KB |
ソースコード
#include <bits/stdc++.h> #define GET_MACRO(a, b, c, NAME, ...) NAME #define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define rep2(i, a) rep3 (i, 0, a) #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__) #define repr2(i, a) repr3 (i, 0, a) #define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--) template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); } template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } using namespace std; typedef long long ll; struct UF { vector<int> parent, size; UF(int n) : parent(n), size(n, 1) { rep (i, n) parent[i] = i; } int root(int x) { if (x == parent[x]) return x; else return parent[x] = root(parent[x]); } void merge(int x, int y) { x = root(x); y = root(y); if (x == y) return; if (size[x] < size[y]) swap(x, y); size[x] += size[y]; parent[y] = x; } bool same(int x, int y) { return root(x) == root(y); } }; struct Stopwatch { double start; Stopwatch() { begin(); } void begin() { start = clock(); } double elapsed() { double end = clock(); double res = (double)(end - start) / CLOCKS_PER_SEC * 1000.0; start = end; return res; } void display(string text) { cerr << text << ":" << elapsed() << "ms" << endl; } }; const int inf = 1e9; int dp0[101010], dp1[101010]; int main() { int n, m; cin >> n >> m; UF uf(n); rep (i, m) { int u, v; scanf("%d %d", &u, &v); u--; v--; uf.merge(u, v); } map<int, int> mp; rep (i, n) if (uf.root(i) == i) mp[uf.size[i]]++; vector<int> a, num; for (auto kv : mp) { a.push_back(kv.first); num.push_back(kv.second); } rep (i, 101010) dp0[i] = dp1[i] = inf; dp0[0] = 0; int sum = 0; vector<multiset<int>> st(101010); vector<int> ord(101010); rep (i, a.size()) { rep (j, sum + 1) { st[j].clear(); dp1[j] = inf; } sum += a[i] * num[i]; rep (j, sum + 1) { if (j - a[i] >= 0) { swap(st[j], st[j - a[i]]); ord[j] = ord[j - a[i]] + 1; } else { ord[j] = 0; } st[j].insert(dp0[j] - ord[j]); if (st[j].size() > num[i] + 1) { int pj = j - (num[i] + 1) * a[i]; auto it = st[j].find(dp0[pj] - ord[pj]); st[j].erase(it); } int cand = *st[j].begin(); chmin(dp1[j], cand + ord[j]); } swap(dp0, dp1); } rep (i, 1, n + 1) { if (dp0[i] > n) dp0[i] = 0; printf("%d\n", dp0[i] - 1); } return 0; }