Submission #1024192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024192		vjudge1	Fireworks (APIO16_fireworks)	C++17	0 / 100	3 ms	7516 KiB

fireworks

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n,m,p,c;
long long r=0;
vector<pair<int,int>>ad[300000];

pair<long long,long long>dfs(int u){
    if(ad[u].empty())return {0,0};
    long long c1=0,c2=0;
    pair<long long,long long>op;
    vector<pair<long long,long long>>t;
    for(auto v:ad[u]){
        t.push_back(dfs(v.first));
        t.back().first+=v.second;
        t.back().second+=v.second;
    }
    sort(t.begin(),t.end());
    if(t.size()&1)op=t[t.size()/2];
    else op={t[t.size()/2-1].second,t[t.size()/2].first};
    if(op.second<op.first)swap(op.first,op.second);
    for(auto v:t){
        c1+=min(abs(op.first-v.first),abs(op.first-v.second));
        c2+=min(abs(op.second-v.first),abs(op.second-v.second));
    }
    if(c1==c2)r+=c1;
    else if(c1<c2)op.second=op.first,r+=c1;
    else op.first=op.second,r+=c2;
    return op;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    #endif
    cin>>n>>m;
    for(int i=2;i<=n+m;i++){
        cin>>p>>c;
        ad[p].push_back({i,c});
    }
    dfs(1);
    cout<<r;
    return 1<<32;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:47:13: warning: left shift count >= width of type [-Wshift-count-overflow]
   47 |     return 1<<32;
      |            ~^~~~
fireworks.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("test.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("test.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45