Submission #963868

#	Time	Username	Problem	Language	Result	Execution time	Memory
963868		new_acc	Fireworks (APIO16_fireworks)	C++14	100 / 100	296 ms	78512 KiB

fireworks

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const ll p=70032301;
const ull p2=913;
const int L=20;
int n,m;
ll t[N],t2[N];
vi graf[N];
multiset<ll>* dfs(int v){
    if(v>n){
        multiset<ll>* xd= new multiset<ll>;
        xd->insert(t[v]);
        xd->insert(t[v]);
        t2[v]=-t[v];
        return xd;
    } 
    multiset<ll>* c=nullptr;
    for(auto u:graf[v]){
        multiset<ll>* x=dfs(u);
        t2[v]+=t2[u];
        if(!c or c->size()<x->size()) swap(c,x); 
        while(x and x->size()){
            c->insert(*(x->begin()));
            x->erase(x->begin());
        }
        delete x;
    }
    for(int i=0;i<graf[v].size()-1;i++){
        auto it=c->end();
        it--;
        t2[v]+=*it;
        c->erase(it);
    }
    t2[v]-=t[v];
    auto it=c->end();
    it--;
    auto it2=c->end();
    it2--,it2--;
    ll v1=*it+t[v],v2=*it2+t[v];
    c->erase(it),c->erase(it2);
    c->insert(v1),c->insert(v2);
    return c;
}
void solve(){
    cin>>n>>m;
    for(int i=2;i<=n+m;i++){
        int a;
        cin>>a>>t[i];
        graf[a].push_back(i);
    }
    multiset<ll>* r=dfs(1);
    auto it=r->end();
    it--;
    cout<<t2[1]+*it<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Compilation message (stderr)

fireworks.cpp: In function 'std::multiset<long long int>* dfs(int)':
fireworks.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<graf[v].size()-1;i++){
      |                 ~^~~~~~~~~~~~~~~~~

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