제출 #975222

#제출 시각아이디문제언어결과실행 시간메모리
975222yoav_s도로 폐쇄 (APIO21_roads)C++17
0 / 100
2084 ms23612 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> v; typedef vector<v> vv; typedef vector<vv> vvv; typedef pair<ll, ll> p; typedef vector<p> vp; typedef vector<vp> vvp; typedef vector<vvp> vvvp; typedef pair<ll, p> tri; typedef vector<tri> vtri; typedef vector<vtri> vvtri; typedef vector<vvtri> vvvtri; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; #define f first #define s second #define pb push_back #define eb emplace_back #define all(v) (v).begin(),(v).end() const ll INF = 1e18; const ll mod = 1e9 + 7; #include "roads.h" void solve(ll cur, vvp &graph, vp &res, ll k, vb &visited) //first = normal, second = without parent { if (visited[cur]) return; visited[cur] = true; for (auto x : graph[cur]) solve(x.f, graph, res, k, visited); ll needToRemove = max(0ll, (ll)graph[cur].size() - k); ll needToRemove2 = max(0ll, needToRemove - 1); v add; ll sum = 0; for (auto x : graph[cur]) { if (res[x.f].f == -1) continue; add.pb(res[x.f].s - res[x.f].f + x.s); sum += res[x.f].f; } sort(all(add)); res[cur] = p(sum, sum); for (ll i = 0; i < needToRemove; i++) res[cur].f += add[i]; for (ll i =0 ; i < needToRemove2; i++) res[cur].s += add[i]; } std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { vvp graph(N); for (ll i = 0; i < N - 1; i++) { graph[U[i]].eb(V[i],W[i]); graph[V[i]].eb(U[i],W[i]); } vector<long long> res(N, -1); ll sum = 0; for (auto x : W) sum += x; res[0] = sum; for (ll i =1; i < N; i++) { vb visited(N, false); vp dp(N, p(-1, -1)); solve(0, graph, dp, i, visited); res[i] = dp[0].f; } return res; } /* int main() { int N; assert(1 == scanf("%d", &N)); std::vector<int> U(N - 1), V(N - 1), W(N - 1); for (int i = 0; i < N - 1; ++i) { assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i])); } std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W); for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) { if (i > 0) { printf(" "); } printf("%lld",closure_costs[i]); } printf("\n"); return 0; } /**/

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

roads.cpp:94:1: warning: "/*" within comment [-Wcomment]
   94 | /**/
      |
#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...