제출 #976683

#제출 시각아이디문제언어결과실행 시간메모리
976683josanneo22도로 폐쇄 (APIO21_roads)C++17
컴파일 에러
0 ms0 KiB
#include "roads.h" #include <vector> #include <bits/stdc++.h> using namespace std; using i64 = long long; #define vi vector<int> vector<i64> N2(int N, vi U, vi V, vi W) { vector<vector<pair<int, int>>> G(N); for (int i = 0; i < N - 1; i++) { G[U[i]].push_back(make_pair(V[i], W[i])); G[V[i]].push_back(make_pair(U[i], W[i])); } auto solve = [&](int k) { // cout << k << '\n'; vector<vector<i64>> dp(N, vector<i64>(2, 100000)); function<void(int, int)> dfs = [&](int u, int f) { // cout << "tree : " << u << ' ' << f << '\n'; // if (G[u].size() < k) { // dp[u][0] = dp[u][1] = 0; // } i64 sum = 0; vector<i64> wait; for (auto & v : G[u]) { if (v.first == f) continue; dfs(v.first, u); wait.push_back(-dp[v.first][1] + dp[v.first][0] + v.second); sum += dp[v.first][0] + v.second; // cout << v.first << ' ' << dp[v.first][0] + v.second << ' ' << dp[v.first][1] << '\n'; } // cout << "total: " << sum << '\n'; sort(wait.begin(), wait.end(), greater<i64>()); // cout << "wait : "; // for (auto & v : wait) cout << v << ' '; // cout << '\n'; int deg = G[u].size(); int remain = deg - max(deg - k - 1, 0); // cout << "remain: " << remain << '\n'; i64 res = sum, S = sum; for (int i = 0; i < min(remain, (int)wait.size()); i++) { S -= wait[i]; res = min(res, S); } dp[u][0] = res; remain = deg - max(deg - k, 0); res = sum; S = sum; // cout << "remain: " << remain << '\n'; // cout << "sums : "; for (int i = 0; i < min(remain, (int)wait.size()); i++) { S -= wait[i]; res = min(res, S); } // cout << '\n'; dp[u][1] = res; // cout << "++++++++++++++\n"; }; dfs(0, -1); // for (int i = 0; i < N; i++) { // cout << "dp : " << i << ' ' << dp[i][0] << ' ' << dp[i][1] << '\n'; // } return dp[0][0]; }; vector<i64> ans(N); for (int k = 0; k < N; k++) { ans[k] = solve(k - 1); } return ans; } vector<i64> juhua(int N, vi U, vi V, vi W) { vector<i64> ans(N); ans[0] = accumulate(W.begin(), W.end(), 0LL); sort(W.begin(), W.end(), greater<int>()); for (int i = 1; i < N; i++) { ans[i] = ans[i - 1] - W[i - 1]; } return ans; } vector<i64> chain(int N, vi U, vi V, vi W) { vector<i64> ans(N); ans[0] = accumulate(W.begin(), W.end(), 0LL); vector<i64> dp(N); for (int i = 0; i < N - 1; i++) { i64 take = (i == 0 ? 0 : dp[i - 1]) + W[i]; i64 dun_take = (i - 2 < 0 ? 0 : dp[i - 2]) + (i - 1 < 0 ? 0 : W[i - 1]); dp[i] = min(take, dun_take); } ans[1] = dp[N - 2]; return ans; } vector<i64> minimum_closure_costs(int N, vi U, vi V, vi W) { if (N <= 5000) return N2(N, U, V, W); if (count(U.begin(), U.end(), 0) == N - 1) return juhua(N, U, V, W); return chain(N, U, V, W); } #include "grader.cpp" /* ST1: 菊花图 直接一个一个贪心移除 ST2: 链 我们可以直接dp, 从i - 1/i - 2转移过来 ST3 & 4: 对于每个K, 我们可以单独solve 就是说如果我们让dp[i] = 整个i的子树里最小价格满足, deg[i] <= k 发现到其实这样的存储方式不足以满足dp转移方式 dp[u][0/1] = 和父亲节点是否有边 如果我们拿这个边那么我们会得到dp[v][1] 如果我们不要这个边我们得到dp[v][0] + W[i] 如果我们现在和父亲节点连边: 需要移除min(deg[u] - k, 0) 没和父亲连边: 需要移除min(deg[u] - k - 1, 0) 那么我们可以拿的边 = deg[u] - 移除 我们先把dp[v][1] - (dp[v][0] + W[i])排序, ans = sum(dp[v][0] + W[i]) 然后我们降序排序然后直接贪心取 O(N ^ 2) 24分 若W[i] = 1, 就是说我们只是求最少移除多少遍使得 max deg <= k erm.... 有没有可能是贪心? 猜测: 如果现在这个边的deg > k, 移除是最优的 然后就是贪心 打了数据,发现不对 */

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccpS8rnD.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccCP17B.o:roads.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status