Submission #761336

#	Time	Username	Problem	Language	Result	Execution time	Memory
761336		Username4132	Fireworks (APIO16_fireworks)	C++14	7 / 100	5 ms	7352 KiB

fireworks

#include<iostream>
#include<vector>
#include<map>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

struct seg{
    ll l, r, value;
    seg(ll L, ll R, ll Value) : l(L), r(R), value(Value) {}
};

seg merge(vector<seg>& els){
    int sum=-((int)els.size());
    bool setl=true, setr=true;
    ll l=0, r=0, value=0;
    map<ll, int> mp;
    for(seg el:els) mp[el.l]++, mp[el.r]++;
    for(pair<ll, int> num:mp){
        sum+=num.S;
        if(sum>=0 && setl) l=num.F, setl=false;
        if(sum>0 && setr) r=num.F, setr=false;
    }
    for(seg el:els){
        value+=el.value;
        value+=max(l-el.r, 0LL);
        value+=max(el.l-l, 0LL);
    }
    return seg(l, r, value);
}

const int MAXN=300010;
int n, m;
vector<pii> g[MAXN];

seg dfs(int v){
    vector<seg> segs;
    for(pii to:g[v]){
        seg partial = dfs(to.F);
        partial.l += to.S;
        partial.r += to.S;
        segs.PB(partial);
    }
    return merge(segs);
}

int main(){
    scanf("%d %d", &n, &m);
    forn(i, n+m-1){
        int a, b; scanf("%d %d", &a, &b);
        g[a-1].PB({i+1, b});
    }
    seg ans = dfs(0);
    printf("%lld\n", ans.value);
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:54:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         int a, b; scanf("%d %d", &a, &b);
      |                   ~~~~~^~~~~~~~~~~~~~~~~

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