oj.uz

Submission #761336

# Submission time Handle Problem Language Result Execution time Memory
761336 2023-06-19T13:57:47 Z Username4132 Fireworks (APIO16_fireworks) C++14
7 / 100
 5 ms 7352 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 5 ms 7252 KB Output is correct
4 Correct 3 ms 7352 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7344 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7244 KB Output is correct
9 Correct 4 ms 7344 KB Output is correct
10 Correct 3 ms 7252 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7344 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Incorrect 3 ms 7264 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 5 ms 7252 KB Output is correct
4 Correct 3 ms 7352 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7344 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7244 KB Output is correct
9 Correct 4 ms 7344 KB Output is correct
10 Correct 3 ms 7252 KB Output is correct
11 Correct 4 ms 7344 KB Output is correct
12 Correct 4 ms 7252 KB Output is correct
13 Incorrect 3 ms 7264 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 5 ms 7252 KB Output is correct
4 Correct 3 ms 7352 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7344 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7244 KB Output is correct
9 Correct 4 ms 7344 KB Output is correct
10 Correct 3 ms 7252 KB Output is correct
11 Correct 4 ms 7344 KB Output is correct
12 Correct 4 ms 7252 KB Output is correct
13 Incorrect 3 ms 7264 KB Output isn't correct
14 Halted 0 ms 0 KB -