제출 #415822

#제출 시각아이디문제언어결과실행 시간메모리
415822flashmt도로 폐쇄 (APIO21_roads)C++17
36 / 100
331 ms10016 KiB
#include <bits/stdc++.h> using namespace std; const long long oo = 1LL << 60; int n; vector<pair<int, int>> a[100100]; long long f[2020]; long long g[2020]; // can keep parent edge void visit(int x, int par, int k) { f[x] = 0; vector<long long> gain; for (auto [y, w] : a[x]) if (y != par) { visit(y, x, k); f[x] += f[y] + w; gain.push_back(g[y] - f[y] - w); } sort(gain.begin(), gain.end()); g[x] = f[x]; for (int i = 0; i < k && i < gain.size(); i++) { if (gain[i] >= 0) break; f[x] += gain[i]; if (i < k - 1) g[x] += gain[i]; } f[x] = min(f[x], g[x]); } vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) { n = N; int isLine = 1; for (int i = 0; i < n - 1; i++) { a[U[i]].push_back({V[i], W[i]}); a[V[i]].push_back({U[i], W[i]}); if (U[i] != i || V[i] != i + 1) isLine = 0; } vector<long long> ans(n); ans[0] = accumulate(W.begin(), W.end(), 0LL); // 1 if (a[0].size() == n - 1) { sort(W.begin(), W.end(), greater<int>()); for (int i = n - 2; i >= 0; i--) ans[i] = ans[i + 1] + W[i]; return ans; } // 2 if (isLine) { vector<long long> f(n, oo); f[0] = 0; f[1] = W[0]; for (int i = 2; i < n; i++) f[i] = min(f[i - 1], f[i - 2]) + W[i - 1]; ans[1] = min(f[n - 1], f[n - 2]); } if (n <= 2000) { for (int i = 1; i < n - 1; i++) { visit(0, -1, i); ans[i] = f[0]; } } return ans; }

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

roads.cpp: In function 'void visit(int, int, int)':
roads.cpp:24:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for (int i = 0; i < k && i < gain.size(); i++)
      |                            ~~^~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:49:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |   if (a[0].size() == n - 1)
      |       ~~~~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...