제출 #976661

#제출 시각아이디문제언어결과실행 시간메모리
976661josanneo22도로 폐쇄 (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> minimum_closure_costs(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; } #include "grader.cpp" /* 对于每个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分 */

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

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