제출 #743612

#제출 시각아이디문제언어결과실행 시간메모리
743612onebit1024도로 폐쇄 (APIO21_roads)C++17
0 / 100
56 ms12108 KiB
#include "roads.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define all(c) c.begin(), c.end() #define endl "\n" const double PI=3.141592653589; void __print(ll x) {cerr << x;} void __print(long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x) #else #define dbg(x...) #endif #include <vector> /* dp[i][j][0] min cost to delete edges such that each node in the subtree of node i has atmost j active edges and the edge from (par[i],i) is still active let's say node i has k edges from it(including parent), if parent is still active then we need to delete to delete k-j down edges otherwise if we are kiling parent edge then k-j-1 down edges to be deleted. cost of deleting edge from u->v is min(dp[v][j][1],dp[v][j][0]+w[u,v]-jth costliest edge of v) cost of keeping edge u->v is min(dp[v][j][0],dp[v][j][1]) sort by decreasing order of keeping-deleting cost and delete the first x */ vector<vector<vector<ll>>>dp; vector<vector<pair<ll,ll>>>adj; vector<vector<ll>>other; ll n; vector<ll>par; void dfs(ll u, ll p){ for(auto &[w,v] : adj[u]){ if(v==p)continue; dfs(v,u); } for(ll j = 0;j<n;++j){ vector<pair<ll,ll>>val; for(auto &[w,v] : adj[u]){ if(v==p)continue; val.pb({min(dp[v][j][0],dp[v][j][1]),dp[v][j][1]}); } ll x = adj[u].size()-j; sort(all(val), [&](auto one,auto two){ return one.first-one.second > two.first - two.second; }); if(u==0){ for(ll i = 0;i<min((ll)val.size(),x);++i)dp[u][j][0]+=val[i].second; for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first; }else if(j>0){ for(ll i = 0;i<min((ll)val.size(),x);++i)dp[u][j][0]+=val[i].second; for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first; } x--; for(ll i = 0;i<min((ll)val.size(),x);++i)dp[u][j][1]+=val[i].second; for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][1] += val[i].first; } } void comp(ll u, ll p){ for(auto &[w,v] : adj[u]){ if(v==p)continue; par[v] = u; for(ll j = 0;j<n;++j)dp[v][j][1] = w; comp(v,u); } } std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n = N; vector<ll>c = {0}; for(ll i = 0;i<n-1;++i)c.pb((ll)W[i]); vector<vector<ll>>dp(n,vector<ll>(2)); dp[0][1] = 1e18; for(ll i = 1;i<n;++i)dp[i][0] = dp[i-1][1],dp[i][1] = c[i]+min(dp[i-1][1],dp[i-1][0]); ll tot = 0; for(auto x : c)tot+=x; vector<ll>res = {tot,min(dp[n-1][0],dp[n-1][1])}; if(n==2)res[1] = 0; for(ll i = 2;i<n;++i)res.pb(0); return res; // n = N; // dp = vector<vector<vector<ll>>>(n+1, vector<vector<ll>>(n+1,vector<ll>(2))); // adj.resize(n+1); // par.resize(n+1); // other.resize(n+1); // for(ll i = 0;i<n-1;++i)adj[U[i]].pb({W[i],V[i]}),adj[V[i]].pb({W[i],U[i]}); // comp(0,-1); // for(ll i = 0;i<n;++i){ // for(auto &[w,v] : adj[i]){ // if(v==par[i])continue; // other[i].pb(w); // } // sort(all(other[i])); // sort(all(adj[i])); // } // for(ll i = 1;i<n;++i)dp[i][0][0] = 1e18; // comp(0,-1); // dfs(0,-1); // vector<ll>res; // for(ll i = 0;i<n;++i)res.pb(dp[0][i][0]); // return res; }

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

roads.cpp: In function 'void dfs(long long int, long long int)':
roads.cpp:76:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |       for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first;
      |                             ~^~~~~~~~~~~
roads.cpp:79:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |       for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first;
      |                             ~^~~~~~~~~~~
roads.cpp:85:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][1] += val[i].first;
      |                           ~^~~~~~~~~~~
#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...