Submission #994722

#	Time	Username	Problem	Language	Result	Execution time	Memory
994722		pavement	Jobs (BOI24_jobs)	C++17	0 / 100	2043 ms	29524 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define int long long

using ll = long long;

int N, s, ans, x[300005], p[300005];
vector<int> adj[300005];

namespace ufds {
	int lnk[300005], sz[300005], l[300005], v[300005];
	
	void init(int n) {
		iota(lnk, lnk + 1 + n, 0);
		fill(sz, sz + 1 + n, 1);
	}
	int find(int x) {
		if (x == lnk[x]) {
			return x;
		}
		return lnk[x] = find(lnk[x]);
	}
	void unite(int a, int b) {
		//~ cout << "MERGE " << a << ' ' << b << '\n';
		a = find(a);
		b = find(b);
		if (a == b) {
			return;
		}
		if (sz[b] > sz[a]) {
			swap(a, b);
		}
		sz[a] += sz[b];
		lnk[b] = a;
	}
};

void pass(int u) {
	if (u && ufds::find(u) != ufds::find(p[u])) {
		int l_p = ufds::l[ufds::find(p[u])];
		int v_p = ufds::v[ufds::find(p[u])];
		int l_u = ufds::l[ufds::find(u)];
		int v_u = ufds::v[ufds::find(u)];
		if (l_p + v_p >= l_u && v_u >= 0) {
			ufds::unite(u, p[u]);
			ufds::l[ufds::find(u)] = l_p;
			ufds::v[ufds::find(u)] = v_p + v_u;
		}
	}
}

void dfs(int u) {
	if (u == ufds::find(u) && ufds::l[ufds::find(u)] > 0) {
		return;
	}
	if (u == ufds::find(u)) {
		//~ cout << "ADD " << u << ' ' << ufds::l[ufds::find(u)] << ' ' << ufds::v[ufds::find(u)] << '\n';
		ans += ufds::v[ufds::find(u)];
	}
	for (auto v : adj[u]) {
		dfs(v);
	}
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> s;
	ufds::l[0] = 0;
	ufds::v[0] = s;
	for (int i = 1; i <= N; i++) {
		cin >> x[i] >> p[i];
		adj[p[i]].pb(i);
		ufds::l[i] = -x[i];
		ufds::v[i] = x[i];
	}
	ufds::init(N);
	for (int rep = 0; rep < N; rep++) {
		for (int i = 1; i <= N; i++) {
			pass(i);
		}
	}
	dfs(0);
	cout << ans - s << '\n';
}

Compilation message (stderr)

Main.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main() {
      | ^~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31