oj.uz

Submission #683947

# Submission time Handle Problem Language Result Execution time Memory
683947 2023-01-19T18:03:19 Z PoonYaPat Fireworks (APIO16_fireworks) C++14
7 / 100
 5 ms 7372 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int n,m;
struct A {
    int L,R;
    ll y_min;
};
vector<pii> adj[300001];

A dfs(int x, int par) {
    priority_queue<int, vector<int>, greater<int>> rsq;
    priority_queue<int> lsq;
    ll Y=0;
    bool ex=true;

    for (auto s : adj[x]) {
        if (s.first==par) continue;
        ex=false;
        A node=dfs(s.first,x);
        Y+=node.y_min;

        if (lsq.size()>0) {
            if (node.L+s.second>rsq.top()) Y+=node.L+s.second-rsq.top();
            if (node.R+s.second<lsq.top()) Y+=lsq.top()-node.R-s.second;
        }

        lsq.push(node.L+s.second); lsq.push(node.R+s.second);
        rsq.push(lsq.top()); lsq.pop();

        while (lsq.top()>rsq.top()) {
            int a=rsq.top(),b=lsq.top();
            lsq.pop(); rsq.pop();
            lsq.push(a); rsq.push(b);
        }

    }

    if (ex) return {0,0,0};
    else return {lsq.top(),rsq.top(),Y};
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=2; i<=n+m; ++i) {
        int a,b; cin>>a>>b;
        adj[i].push_back(pii(a,b));
        adj[a].push_back(pii(i,b));
    }
    cout<<dfs(1,0).y_min;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7364 KB Output is correct
9 Correct 4 ms 7252 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 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Incorrect 4 ms 7252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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