Submission #367908

#	Time	Username	Problem	Language	Result	Execution time	Memory
367908		AriaH	Fireworks (APIO16_fireworks)	C++11	7 / 100	12 ms	14572 KiB

fireworks

#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 (stderr)

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 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45