제출 #531351

#제출 시각아이디문제언어결과실행 시간메모리
531351NhatMinh0208도로 폐쇄 (APIO21_roads)C++14
7 / 100
2083 ms38788 KiB
#ifndef CPL_TEMPLATE #define CPL_TEMPLATE /* Normie's Template v2.5 Changes: Added warning against using pragmas on USACO. */ // Standard library in one include. #include <bits/stdc++.h> using namespace std; // ordered_set library. // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; // #define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update> // AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.) //#include <atcoder/all> //using namespace atcoder; //Pragmas (Comment out these three lines if you're submitting in szkopul or USACO.) // #pragma comment(linker, "/stack:200000000") // #pragma GCC optimize("Ofast,unroll-loops,tree-vectorize") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") //File I/O. #define FILE_IN "cseq.inp" #define FILE_OUT "cseq.out" #define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout) //Fast I/O. #define fio ios::sync_with_stdio(0);cin.tie(0) #define nfio cin.tie(0) #define endl "\n" //Order checking. #define ord(a,b,c) ((a>=b)and(b>=c)) //min/max redefines, so i dont have to resolve annoying compile errors. #define min(a,b) (((a)<(b))?(a):(b)) #define max(a,b) (((a)>(b))?(a):(b)) // Fast min/max assigns to use with AVX. // Requires g++ 9.2.0. // template<typename T> // __attribute__((always_inline)) void chkmin(T& a, const T& b) { // a=(a<b)?a:b; // } // template<typename T> // __attribute__((always_inline)) void chkmax(T& a, const T& b) { // a=(a>b)?a:b; // } //Constants. #define MOD (ll(998244353)) #define MAX 300001 #define mag 320 const long double PI=3.14159265358979; //Pairs and 3-pairs. #define p1 first #define p2 second.first #define p3 second.second #define fi first #define se second #define pii(element_type) pair<element_type,element_type> #define piii(element_type) pair<element_type,pii(element_type)> //Quick power of 2. #define pow2(x) (ll(1)<<x) //Short for-loops. #define ff(i,__,___) for(int i=__;i<=___;i++) #define rr(i,__,___) for(int i=__;i>=___;i--) //Typedefs. #define bi BigInt typedef long long ll; typedef long double ld; typedef short sh; // Binpow and stuff ll BOW(ll a, ll x, ll p) { if (!x) return 1; ll res=BOW(a,x/2,p); res*=res; res%=p; if (x%2) res*=a; return res%p; } ll INV(ll a, ll p) { return BOW(a,p-2,p); } //---------END-------// #endif #include "roads.h" vector<pii(ll)> gt[100001]; pii(ll) par[100001]; vector<pii(ll)> val[100001]; ll las[100001]; ll why[100001]; ll n,m,i,j,k,t,t1,u,v,a,b; int dfs(int x) { // cout<<"dfs "<<x<<endl; vector<int> ch; for (auto g : gt[x]) if (g.fi-par[x].fi) { par[g.fi]={x,g.se}; ch.push_back(dfs(g.fi)); } sort(ch.begin(), ch.end(), [](int a, int b){ return (val[a].size()>val[b].size()); }); int u=ch.size(); if (u==0) { val[x]={{par[x].se,1e14+7}}; las[x]=1; why[x]=x; // cout<<"val "<<x<<endl; // for (auto g : val[x]) cout<<g.fi<<','<<g.se<<' '; cout<<endl; return x; } else { for (int i=0;i<max(val[ch[0]].size(),gt[x].size());i++) { // cout<<"u "<<u<<endl; while(u && i>=val[ch[u-1]].size()) u--; if (u==1 && i>=las[ch[0]] && i>=gt[x].size()) break; // cout<<"calc "<<x<<' '<<i<<endl; if (i==0) { // cout<<"c0 "<<u<<endl; for (int j=1;j<u;j++) val[ch[0]][0].fi+=val[ch[j]][0].fi; val[ch[0]][0].fi+=par[x].se; } else if (i<gt[x].size()) { ll a = 0; priority_queue<ll,vector<ll>,greater<ll>> pq; for (int j=0;j<u;j++) {a+=val[ch[j]][i].fi; pq.push(val[ch[j]][i].se);} for (int j=u;j<ch.size();j++) { a+=par[why[ch[j]]].se; pq.push(-par[why[ch[j]]].se); } for (int j=0;j<i-1;j++) if (pq.size() && pq.top()<0) { a+=pq.top(); pq.pop(); } pii(ll) sus; sus.se=a; if (pq.size() && pq.top()<0) { a+=pq.top(); pq.pop(); } a+=par[x].se; sus.fi=a; sus.se-=sus.fi; if (val[ch[0]].size()>i) val[ch[0]][i]=sus; else val[ch[0]].push_back(sus); } else { val[ch[0]][i].fi+=min(0,val[ch[0]][i].se); val[ch[0]][i].se=0; for (int j=1;j<u;j++) { val[ch[0]][i].fi+=val[ch[j]][i].fi; val[ch[0]][i].fi+=min(0,val[ch[j]][i].se); } } } las[ch[0]]=gt[x].size(); why[ch[0]]=x; // cout<<"val "<<x<<endl; // for (auto g : val[ch[0]]) cout<<g.fi<<','<<g.se<<' '; cout<<endl; return ch[0]; } } vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) { n=N; for (i=0;i<n-1;i++) { gt[U[i]+1].push_back({V[i]+1,W[i]}); gt[V[i]+1].push_back({U[i]+1,W[i]}); } gt[1].push_back({0,0}); int t = dfs(1); vector<ll> res; for (i=0;i<n;i++) if (i<val[t].size()) res.push_back(val[t][i].fi+min(0,val[t][i].se)); else res.push_back(0); return res; } // a;

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

roads.cpp: In function 'int dfs(int)':
roads.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i=0;i<max(val[ch[0]].size(),gt[x].size());i++) {
      |                   ^
roads.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |       while(u && i>=val[ch[u-1]].size()) u--;
      |                  ~^~~~~~~~~~~~~~~~~~~~~
roads.cpp:137:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |       if (u==1 && i>=las[ch[0]] && i>=gt[x].size()) break;
      |                                    ~^~~~~~~~~~~~~~
roads.cpp:144:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |       else if (i<gt[x].size()) {
      |                ~^~~~~~~~~~~~~
roads.cpp:148:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for (int j=u;j<ch.size();j++) {
      |                      ~^~~~~~~~~~
roads.cpp:165:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  165 |         if (val[ch[0]].size()>i) val[ch[0]][i]=sus; else val[ch[0]].push_back(sus);
      |             ~~~~~~~~~~~~~~~~~^~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:195:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |   for (i=0;i<n;i++) if (i<val[t].size()) res.push_back(val[t][i].fi+min(0,val[t][i].se));
      |                         ~^~~~~~~~~~~~~~
#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...