oj.uz

Submission #367908

# Submission time Handle Problem Language Result Execution time Memory
367908 2021-02-18T19:36:13 Z AriaH Fireworks (APIO16_fireworks) C++11
7 / 100
 12 ms 14572 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 = 6e5 + 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;
    for (pll u : adj[v])
    {
        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));
    }
    sort(all(seg));
	int cnt = 0;
	for(auto x : seg)
	{
		cntl[cnt] = cntr[cnt] = psL[cnt] = psR[cnt] = 0;
		cnt ++;
	}
	cntl[cnt] = cntr[cnt] = psL[cnt] = psR[cnt] = 0;
    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;
   	/*printf("node = %d\n", v);
	for(int i = 0; i < (int)seg.size(); i ++)
	{
		printf("%lld %lld   ", seg[i].F, seg[i].S);
	}
	printf("\n"); */
	for(int i = 0; i < (int)seg.size(); i ++)
    {
		///printf("%lld %lld   ", psL[i], psR[i]);
        ll cu = psL[i] + psR[i];
        if(cu < mn)
        {
            mn = cu;
            l = seg[i].F;
            r = seg[i].F;
        }
		else if(cu == mn) l = min(l, seg[i].F), r = max(r, seg[i].F);
    }
	///printf("\n mn = %lld res = %lld l = %lld r = %lld\n", mn, res, l, r);
	res += mn;
    return Mp(l, r);
}

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

Compilation message

fireworks.cpp: In function 'std::pair<long long int, long long int> DFS(int)':
fireworks.cpp:32:11: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   32 |  for(auto x : seg)
      |           ^
fireworks.cpp: In function 'int main()':
fireworks.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:82:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |         ll p, c; scanf("%lld%lld", &p, &c);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 11 ms 14444 KB Output is correct
9 Correct 10 ms 14572 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Incorrect 11 ms 14444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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