oj.uz

Submission #367890

# Submission time Handle Problem Language Result Execution time Memory
367890 2021-02-18T18:41:09 Z AriaH Fireworks (APIO16_fireworks) C++11
7 / 100
 6 ms 7424 KB 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define all(x)                        x.begin(), x.end()
#define Mp                            make_pair

const int N = 3e5 + 10;
const ll inf = 1e18;
ll res; int n, m;
vector<pll> adj[N];

ll psL[N], psR[N], cntl[N], cntr[N];

pair<ll, ll> DFS(int v) {
    if (!SZ(adj[v])) return {0, 0};
    vector < pll > seg;
    int cnt = 0;
    for (pll u : adj[v])
    {
        psL[cnt] = 0;
        psR[cnt] = 0;
        cntl[cnt] = 0;
        cntr[cnt] = 0;
        cnt ++;
        pll x = DFS(u.F);
        x.F += u.S, x.S += u.S;
        seg.push_back(Mp(x.F, 0));
        seg.push_back(Mp(x.S, 1));
    }
    psL[cnt] = psR[cnt] = cntl[cnt] = cntr[cnt] = 0;
    sort(all(seg));
    for(int i = 0; i < (int)seg.size(); i ++)
    {
        if(i) cntl[i] = cntl[i - 1], psL[i] = psL[i - 1] + cntl[i - 1] * (seg[i].F - seg[i - 1].F);
        if(seg[i].S == 1)
        {
            cntl[i] ++;
        }
    }
    for(int i = (int)seg.size() - 1; ~i; i --)
    {
        if(i + 1 < (int)seg.size())
        {
            cntr[i] = cntr[i + 1];
            psR[i] = psR[i + 1] + cntr[i + 1] * (seg[i + 1].F - seg[i].F);
        }
        if(seg[i].S == 0) cntr[i] ++;
    }
    ll mn = inf, l = inf, r = -inf;
    for(int i = 0; i < (int)seg.size(); i ++)
    {
        ll cu = psL[i] + psR[i];
        if(cu < mn)
        {
            mn = cu;
            l = min(l, seg[i].F);
            r = max(r, seg[i].F);
        }
    }
	res += mn;
    return Mp(l, r);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n + m; i++) {
        int p, c; scanf("%d%d", &p, &c);
        adj[p].push_back({i, c});
    }
    DFS(1);
    printf("%lld\n", res);
    return 0;
}

Compilation message

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

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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