oj.uz

Submission #684428

# Submission time Handle Problem Language Result Execution time Memory
684428 2023-01-21T06:54:11 Z PoonYaPat Fireworks (APIO16_fireworks) C++14
7 / 100
 14 ms 26196 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m;
ll l[300001],r[300001],w[300001],Ymin[300001];
vector<int> adj[300001];
priority_queue<ll, vector<ll>, greater<ll>> rsq[300001],temp;
priority_queue<ll> lsq[300001];

void dfs(int x) {
    int cnt=0;

    if (!adj[x].size()) {

        l[x]=w[x]; r[x]=w[x];
        Ymin[x]=0;
        lsq[x].push(l[x]);
        rsq[x].push(r[x]);
        return;
    }

    for (auto s : adj[x]) {
        ++cnt;
        dfs(s);

        Ymin[x]+=Ymin[s];

        if (lsq[x].size()) {
            if (l[s]>r[x]) Ymin[x]+=l[s]-r[x];
            if (r[s]<l[x]) Ymin[x]+=l[x]-r[s];
        }

        if (lsq[s].size()+rsq[s].size()>lsq[x].size()+temp.size()) swap(lsq[x],lsq[s]), swap(temp,rsq[s]);

        while (!lsq[s].empty()) {
            if (lsq[s].top()>=temp.top()) temp.push(lsq[s].top());
            else lsq[x].push(lsq[s].top());
            lsq[s].pop();
        }

        while (!rsq[s].empty()) {
            if (rsq[s].top()>=temp.top()) temp.push(rsq[s].top());
            else lsq[x].push(rsq[s].top());
            rsq[s].pop();
        }

        while (temp.size()>cnt) lsq[x].push(temp.top()), temp.pop();
        while (temp.size()<cnt) temp.push(lsq[x].top()), lsq[x].pop();

        l[x]=lsq[x].top();
        r[x]=temp.top();

    }

    l[x]=lsq[x].top()+w[x];
    r[x]=temp.top()+w[x];
    lsq[x].pop(); lsq[x].push(l[x]);
    rsq[x].push(r[x]);

    while (temp.size()) temp.pop();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=2; i<=n+m; ++i) {
        int u; cin>>u>>w[i];
        adj[u].push_back(i);
    }
    dfs(1);
    cout<<Ymin[1];
}

Compilation message

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:48:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         while (temp.size()>cnt) lsq[x].push(temp.top()), temp.pop();
      |                ~~~~~~~~~~~^~~~
fireworks.cpp:49:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         while (temp.size()<cnt) temp.push(lsq[x].top()), lsq[x].pop();
      |                ~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26068 KB Output is correct
2 Correct 13 ms 26068 KB Output is correct
3 Correct 13 ms 26196 KB Output is correct
4 Correct 14 ms 26164 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26196 KB Output is correct
8 Correct 13 ms 26172 KB Output is correct
9 Correct 13 ms 26196 KB Output is correct
10 Correct 13 ms 26068 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26068 KB Output is correct
2 Correct 13 ms 26068 KB Output is correct
3 Correct 13 ms 26196 KB Output is correct
4 Correct 14 ms 26164 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26196 KB Output is correct
8 Correct 13 ms 26172 KB Output is correct
9 Correct 13 ms 26196 KB Output is correct
10 Correct 13 ms 26068 KB Output is correct
11 Incorrect 13 ms 26132 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26068 KB Output is correct
2 Correct 13 ms 26068 KB Output is correct
3 Correct 13 ms 26196 KB Output is correct
4 Correct 14 ms 26164 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26196 KB Output is correct
8 Correct 13 ms 26172 KB Output is correct
9 Correct 13 ms 26196 KB Output is correct
10 Correct 13 ms 26068 KB Output is correct
11 Incorrect 13 ms 26132 KB Output isn't correct
12 Halted 0 ms 0 KB -