제출 #559490

#제출 시각아이디문제언어결과실행 시간메모리
559490fcmalkcin도로 폐쇄 (APIO21_roads)C++17
24 / 100
2095 ms32664 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back #define endl "\n" mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn=5e5+50; const ll mod=1e9+7 ; const ll base=1e18; /// i believe myself /// goal 0/7 #include "roads.h" vector<pll> adj[maxn]; ll dp[maxn][2]; ll k; void dfs(ll u,ll par,ll w) { ll cnt=0; ll sl=0; dp[u][0]+=w; if (k==0) dp[u][1]=base; vector<ll> vt; for (auto p:adj[u]) { ll to=p.ff; if (to==par) continue; dfs(to,u,p.ss); if (dp[to][0]<=dp[to][1]) { dp[u][0]+=dp[to][0]; dp[u][1]+=dp[to][0]; } else { sl++; dp[u][0]+=dp[to][1]; dp[u][1]+=dp[to][1]; vt.pb(dp[to][0]-dp[to][1]); } } sort(vt.begin(),vt.end()); ll p=sl-k; for (int i=0;i<p;i++) dp[u][0]+=vt[i]; if (k) for (int i=0;i<p+1;i++) dp[u][1]+=vt[i]; } vector<ll> minimum_closure_costs(int N, vector<int> U,vector<int> V,vector<int> W) { ll n=N; for (int i=0;i<U.size();i++) { adj[U[i]+1].pb(make_pair(V[i]+1,W[i])); adj[V[i]+1].pb(make_pair(U[i]+1,W[i])); } vector<ll> res; for (int i=0;i<=n-1;i++) { for (int t=0;t<=n;t++) for (int p=0;p<=1;p++) dp[t][p]=0; k=i; dfs(1,0,0); res.pb(dp[1][0]); } return res; } /*int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("t.inp", "r")) { freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n; vector<ll> p,p1,p2; cin>> n; for (int i=1;i<=n-1;i++) { ll x, y, w; cin>> x>> y>> w; p.pb(x); p1.pb(y); p2.pb(w); } vector<ll> res=minimum_closure_costs(n, p,p1,p2); for (auto to:res) cout <<to<<" "; }*/ /* 5 0 1 1 0 2 4 0 3 3 2 4 2 */

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

roads.cpp: In function 'void dfs(long long int, long long int, long long int)':
roads.cpp:27:8: warning: unused variable 'cnt' [-Wunused-variable]
   27 |     ll cnt=0;
      |        ^~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i=0;i<U.size();i++)
      |                  ~^~~~~~~~~
#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...