Submission #113981

#	Time	Username	Problem	Language	Result	Execution time	Memory
113981		patrikpavic2	Fireworks (APIO16_fireworks)	C++17	100 / 100	645 ms	75768 KiB

fireworks

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <set>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < ll, ll > pll;
typedef pair < pll, ll > ppl;
typedef vector < int > vi;
typedef vector < pll > vl;
typedef vector < ll > vll;
typedef pair < vll, ll > pvl;

const int N = 3e5 + 500;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

vi v[N];
ll tez[N], ans[N], sum[N], ng[N];
multiset < ll > s[N];
int n, m;

void f(int x){
    if(v[x].size() == 0){
        sum[x] = tez[x];
        s[x].insert(tez[x]);
        s[x].insert(tez[x]);
        ng[x] = -1;
        return;
    }
    ll bs = 0, mini = 0;
    vll ret;
    sum[x] = tez[x];
    //printf("X = %d\n", x);
    for(int y : v[x]){
        f(y);
        sum[x] += sum[y];
        ng[x] += ng[y];
        if(s[x].size() < s[y].size()){
            swap(s[x], s[y]);
        }
        for(ll a : s[y]) s[x].insert(a);
        s[y].clear();
    }
    //printf("X = %d NG %d\n", x, ng[x]);
    while(s[x].size() > 1 - ng[x]) s[x].erase(--s[x].end());
    //printf("X = %d\n", x);
    ll a = *s[x].rbegin(); s[x].erase(s[x].lower_bound(a));
    ll b = *s[x].rbegin(); s[x].erase(s[x].lower_bound(b));
    //printf("X = %d\n", x);
    s[x].insert(a + tez[x]); s[x].insert(b + tez[x]);
    //printf("RET{%d}: ", (int)ret.size());
    //for(int xx : s[x]) printf("%d ", xx);
    //printf("\n");
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 2;i <= n + m;i++){
        int x, y; scanf("%d%d", &x, &y);
        v[x].PB(i); tez[i] = y;
    }
    f(1);
    ll ans = sum[1], lst = 0, nag = ng[1];
    //printf("siz %d\n", s[1].size());
    for(ll x : s[1]){
        //printf(" %d", x);
        ans += (x - lst) * nag;
        nag++;
        if(!nag) printf("%lld\n", ans);
        lst = x;
    }
    //printf("\n");


}

Compilation message (stderr)

fireworks.cpp: In function 'void f(int)':
fireworks.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(s[x].size() > 1 - ng[x]) s[x].erase(--s[x].end());
           ~~~~~~~~~~~~^~~~~~~~~~~
fireworks.cpp:38:8: warning: unused variable 'bs' [-Wunused-variable]
     ll bs = 0, mini = 0;
        ^~
fireworks.cpp:38:16: warning: unused variable 'mini' [-Wunused-variable]
     ll bs = 0, mini = 0;
                ^~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:67:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y; scanf("%d%d", &x, &y);
                   ~~~~~^~~~~~~~~~~~~~~~

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