Submission #40037

#	Time	Username	Problem	Language	Result	Execution time	Memory
40037		fest	Fireworks (APIO16_fireworks)	C++14	0 / 100	5 ms	11612 KiB

fireworks

// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef COMP
		freopen(".in", "r", stdin);
		freopen("1.out", "w", stdout);
	#else
		freopen(FILENAME".in", "r", stdin);
		freopen(FILENAME".out", "w", stdout);
	#endif
}                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 200500, inf = 1e9 * 2, MOD = (int)1e9 + 7;

char CH[N];

const ll INF = 1e18;

const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};

ll mn[N], l[N], r[N];

vector<pair<int, ll> > g[N];

void dfs(int v) {
	mn[v] = INF;
	l[v] = INF, r[v] = INF;
	if (SZ(g[v]) == 0) {
		mn[v] = 0;
		l[v] = 0, r[v] = 0;
		return;
	}
	for (auto i : g[v]) {
		int u = i.F;
		ll c = i.S;
		dfs(u);       
		l[u] += c;
		r[u] += c;
		if (mn[v] == INF) {
			mn[v] = mn[u];
			l[v] = l[u];
			r[v] = r[u];
			continue;
		}
		mn[v] += mn[u];
		if (r[v] < l[u]) {
			mn[v] += l[u] - r[v];
			l[v] = r[v];
			r[v] = l[u];
			continue;
		}
		if (r[u] < l[v]) {
			mn[v] += l[v] - r[u];
			r[v] = l[v];
			l[v] = r[u];
			continue;
		}
		l[v] = max(l[v], l[u]);
		r[v] = min(r[v], r[u]);
	}
} 	

int main() {
  
	int n, m;
	cin >> n >> m;
	for (int i = 2; i <= n + m; i++) {
		int x;
		ll c;
		scanf("%d %lld", &x, &c);
		g[x].pb({i, c});
	}
	dfs(1);
	for (int i = 1; i <= n + m; i++) cerr << mn[i] << " ";
	printf("%lld", mn[1]);
	return 0;	
}

Compilation message (stderr)

fireworks.cpp: In function 'void FREOPEN()':
fireworks.cpp:25:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".in", "r", stdin);
                                     ^
fireworks.cpp:26:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".out", "w", stdout);
                                       ^
fireworks.cpp: In function 'int main()':
fireworks.cpp:90:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %lld", &x, &c);
                           ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45