제출 #955749

#제출 시각아이디문제언어결과실행 시간메모리
955749caterpillow도로 폐쇄 (APIO21_roads)C++17
0 / 100
2031 ms11868 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pl = pair<ll, ll>; #define vt vector #define f first #define s second #define all(x) x.begin(), x.end() #define pb push_back #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define F0R(i, b) FOR (i, 0, b) #define endl '\n' #define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0) const ll INF = 1e12; int n; vt<vt<pl>> adj; vt<ll> ans; pl dfs(int u, int k, int par = -1) { // {take parent edge, dont take parent edge} vt<ll> diff; ll take_cost = 0; for (auto [v, w] : adj[u]) { if (v == par) continue; auto [take, dont_take] = dfs(v, k, u); take_cost += dont_take; diff.pb(take - dont_take + w); } ll dont_take_cost = take_cost; ll req = adj[u].size() - k; sort(all(diff)); int i = 0; while (i < diff.size() && diff[i] < 0) { dont_take_cost += diff[i]; take_cost += diff[i]; i++; } for (; i < req - 1; i++) { dont_take_cost += diff[i]; take_cost += diff[i]; } if (i == req - 1) { if (diff.size() <= req - 1) { dont_take_cost += INF; } else { dont_take_cost += diff[req - 1]; } } return {take_cost, dont_take_cost}; } vt<ll> minimum_closure_costs(int _n, vt<int> u, vt<int> v, vt<int> w) { n = _n; adj.resize(n); F0R (i, n - 1) { adj[u[i]].pb({v[i], w[i]}); adj[v[i]].pb({u[i], w[i]}); } ans.resize(n); ROF (k, 0, n) { ans[k] = dfs(4, k).s; } return ans; }

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

roads.cpp: In function 'pl dfs(int, int, int)':
roads.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while (i < diff.size() && diff[i] < 0) {
      |            ~~^~~~~~~~~~~~~
roads.cpp:53:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   53 |         if (diff.size() <= req - 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...