제출 #208726

#제출 시각아이디문제언어결과실행 시간메모리
208726junodeveloperFireworks (APIO16_fireworks)C++17
26 / 100
11 ms7444 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define sz(x) ((int)x.size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define fi first #define se second #define mset(x,y) memset(x,y,sizeof(x)) #define rep(i,a,b) for(int i(a);i<=(b);i++) #define repr(i,a,b) for(int i(a);i>=(b);i--) using namespace std; #ifdef LOCAL #define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__) #else #define dmp(...) (__VA_ARGS__) #endif template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;} template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){ while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...); } using namespace __gnu_pbds; using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; int n,m; int p[300010],c[300010]; ll ans[300010],up[300010]; vi adj[300010]; priority_queue<ll>* pq[300010]; void merge(int u,int v) { while(!pq[v]->empty()) { pq[u]->push(pq[v]->top()); pq[v]->pop(); } ans[u]+=ans[v]; } void adjust(int u) { up[u]+=c[u]; int top=pq[u]->top(); pq[u]->pop(); pq[u]->push(top+c[u]); } void debug(int u) { priority_queue<int> b; cout<<"u:"<<u<<",ans:"<<ans[u]<<",up:"<<up[u]<<",pq:"; while(!pq[u]->empty())b.push(pq[u]->top()),pq[u]->pop(); while(!b.empty()) { ll it=b.top();b.pop(); cout<<it<<' '; pq[u]->push(it); }cout<<endl; } void solve(int u) { if(adj[u].empty()) { pq[u]=new priority_queue<ll>(); pq[u]->push(0); up[u]=0; return; } int mx=-1,id=0; vector<ll> ups; for(auto& it:adj[u]) { solve(it); adjust(it); if(mx<sz((*pq[it]))) { mx=sz((*pq[it])); id=it; } ups.pb(up[it]); } for(auto& it:adj[u]) { if(it==id)continue; merge(id,it); } pq[u]=pq[id]; ans[u]=ans[id]; up[u]=up[id]; sort(all(ups));reverse(all(ups)); up[u]=1e18; for(auto& it:ups) { if(it>=pq[id]->top()) { up[u]=it; } else { ans[u]+=pq[id]->top()-it; up[u]=pq[id]->top(); pq[id]->pop(); pq[id]->push(it); } } //debug(u); } void MAIN() { int i,j; cin>>n>>m; for(i=2;i<=n+m;i++) { cin>>p[i]>>c[i]; adj[p[i]].pb(i); } solve(1); cout<<ans[1]; } int main() { ios::sync_with_stdio(false);cin.tie(0); int T=1; //cin>>T; for(int tt=1;tt<=T;tt++) { MAIN(); } return 0; }

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

fireworks.cpp: In function 'void _dmp(const char*, TH, TA ...)':
fireworks.cpp:20:1: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
 while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
 ^~~~~
fireworks.cpp:20:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
 while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
                                ^~~~
fireworks.cpp: In function 'void MAIN()':
fireworks.cpp:97:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...