oj.uz

Submission #402621

# Submission time Handle Problem Language Result Execution time Memory
402621 2021-05-12T04:46:51 Z qwerasdfzxcl Fireworks (APIO16_fireworks) C++14
7 / 100
 5 ms 7372 KB 
#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;
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 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);
        idx[s] = (int)st.size()-1;
        dp[s] = cur;
        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");
}

ll myabs(ll x){
    if (x<0) return -x;
    return x;
}

void dfs2(int s){
    if (adj[s].empty()) return;
    for (auto &v:adj[s]){
        dfs2(v.first);
        ans[s] += myabs(dp[v.first]-dp[s])+ans[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);
    dfs2(1);
    //for (int i=1;i<=n+m;i++) printf("%lld ", dp[i]);
    //printf("\n");
    printf("%lld\n", ans[1]);
    return 0;
}

Compilation message

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

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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