oj.uz

Submission #367901

# Submission time Handle Problem Language Result Execution time Memory
367901 2021-02-18T18:58:17 Z AriaH Fireworks (APIO16_fireworks) C++11
7 / 100
 6 ms 7532 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;
    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 = 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++) {
        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 '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:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |         int p, c; scanf("%d%d", &p, &c);
      |                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7532 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 5 ms 7404 KB Output is correct
7 Correct 6 ms 7404 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 6 ms 7404 KB Output is correct
10 Correct 5 ms 7404 KB Output is correct
11 Correct 5 ms 7532 KB Output is correct
12 Incorrect 5 ms 7404 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7532 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 5 ms 7404 KB Output is correct
7 Correct 6 ms 7404 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 6 ms 7404 KB Output is correct
10 Correct 5 ms 7404 KB Output is correct
11 Correct 5 ms 7532 KB Output is correct
12 Incorrect 5 ms 7404 KB Output isn't correct
13 Halted 0 ms 0 KB -