Submission #402628

#	Time	Username	Problem	Language	Result	Execution time	Memory
402628		qwerasdfzxcl	Fireworks (APIO16_fireworks)	C++14	100 / 100	1058 ms	194728 KiB

fireworks

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Line{
    ll x, y, a;
    Line(){}
    Line(ll _x, ll _y, ll _a): x(_x), y(_y), a(_a) {}
    bool operator<(const Line &L) const{
        if (x==L.x) return a<L.a;
        return x<L.x;
    }
};
struct Graph{
    multiset<ll> pt;
    ll of, mx;
    Graph() {}
};
vector<Graph> st, ts;
vector<pair<int, int>> adj[300300];
int idx[300300];
ll dp[300300], ans[300300];

void st_merge(int v, int w){
    st[v].mx += st[w].mx;
    for (auto val:st[w].pt){
        st[v].pt.insert(val-st[w].of+st[v].of);
    }
}

void ts_merge(int v, int w){
    ts[v].mx += ts[w].mx;
    for (auto val:ts[w].pt){
        ts[v].pt.insert(val-ts[w].of+ts[v].of);
    }
}

void dfs(int s, ll cur){
    if(adj[s].empty()){
        Graph tmp;
        tmp.of = 0, tmp.mx = 1;
        tmp.pt.insert(cur);
        tmp.pt.insert(cur);
        st.push_back(tmp);
        ts.push_back(tmp);
        idx[s] = (int)st.size()-1;
        dp[s] = cur;
        ans[s] = 0;
        return;
    }
    for (auto &v:adj[s]) dfs(v.first, cur+v.second);
    for (auto &v:adj[s]){
        //printf("%d %d %d\n", s, idx[v.first], st[idx[v.first]].pt.size());
        st[idx[v.first]].of += v.second;
        for (int i=2;i<=st[idx[v.first]].mx;i++) st[idx[v.first]].pt.erase(--st[idx[v.first]].pt.end());
        st[idx[v.first]].mx = 1;
        vector<ll> tmp;
        for (int i=0;i<2;i++){
            tmp.push_back(*(--st[idx[v.first]].pt.end()));
            tmp.back() += v.second;
            st[idx[v.first]].pt.erase(--st[idx[v.first]].pt.end());
        }
        for (int i=0;i<2;i++) st[idx[v.first]].pt.insert(tmp[i]);
    }
    int mx = 0;
    for (auto &v:adj[s]) if (mx<(int)st[idx[v.first]].pt.size()) mx = (int)st[idx[v.first]].pt.size(), idx[s] = idx[v.first];
    for (auto &v:adj[s]) if (idx[s]!=idx[v.first]) st_merge(idx[s], idx[v.first]);
    auto iter = st[idx[s]].pt.end();
    for (int i=st[idx[s]].mx;i>=0;i--) --iter;
    dp[s] = (*iter)-st[idx[s]].of;
    //printf("%d %lld\n", s, dp[s]);
    //printf("%lld\n", st[idx[s]].of);
    //for (auto &val:st[idx[s]].pt) printf("%lld ", val);
    //printf("\n");

    for (auto &v:adj[s]){
        //printf("%d %d %d\n", s, idx[v.first], st[idx[v.first]].pt.size());
        ts[idx[v.first]].of += v.second;
        for (int i=2;i<=ts[idx[v.first]].mx;i++) ts[idx[v.first]].pt.erase(--ts[idx[v.first]].pt.end());
        ts[idx[v.first]].mx = 1;
        vector<ll> tmp;
        for (int i=0;i<2;i++){
            tmp.push_back(*(--ts[idx[v.first]].pt.end()));
            tmp.back() += v.second;
            ts[idx[v.first]].pt.erase(--ts[idx[v.first]].pt.end());
        }
        for (int i=0;i<2;i++) ts[idx[v.first]].pt.insert(tmp[i]);
        if (*(--ts[idx[v.first]].pt.end())<=dp[s]+ts[idx[v.first]].of) ans[s] += ans[v.first]+(dp[s]+ts[idx[v.first]].of-*(--ts[idx[v.first]].pt.end()));
        else{
            auto iter = --ts[idx[v.first]].pt.end();
            ll tval = ans[v.first], d=1;
            while(iter!=ts[idx[v.first]].pt.begin() && *iter>dp[s]+ts[idx[v.first]].of){
                --iter, --d;
                auto tmpiter = iter;
                ++tmpiter;
                tval += d*(*iter-*tmpiter);
            }
            if (*iter>dp[s]+ts[idx[v.first]].of){
                --d;
                tval += d*(dp[s]+ts[idx[v.first]].of-(*iter));
            }
            else{
                tval += d*(dp[s]+ts[idx[v.first]].of-(*iter));
            }
            ans[s] += tval;
        }
    }
    for (auto &v:adj[s]) if (idx[s]!=idx[v.first]) ts_merge(idx[s], idx[v.first]);
}


int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    fill(idx, idx+n+m+1, -1);
    for (int i=2;i<=n+m;i++){
        int p, c;
        scanf("%d %d", &p, &c);
        adj[p].push_back({i, c});
    }
    dfs(1, 0);
    //for (int i=1;i<=n+m;i++) printf("%lld ", dp[i]);
    //printf("\n");
    printf("%lld\n", ans[1]);
    return 0;
}

Compilation message (stderr)

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

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