Submission #494930

#	Time	Username	Problem	Language	Result	Execution time	Memory
494930		YJU	Magic Tree (CEOI19_magictree)	C++14	34 / 100	812 ms	1048580 KiB

magictree

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops, no-stack-protector, Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll INF = (1LL<<60);
const ll N = 1e6 + 5;
const ll MOD = 1e9 + 7;
const ld pi = acos(-1);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
#define setp setprecision

typedef map<ll, ll> mll;
// FOR DEBUG PURPOSE

ostream& operator << (ostream& out, mll k) {
	for (auto i : k) {
		out << "{" << i.fi << ", " << i.se << "} ";
	}
	return out;
}

ll d[N], w[N], n, m, t;
vector<ll> v[N];
mll dp[N];

void insert(mll &a, pll k) {
	ll last = k.se;
	for (auto i = a.lwb(k.fi+1);i != a.end(); i = a.lwb(i->fi+1)) {
		if (i->se > last) {
			i->se -= last;
			break;
		} else {
			last -= i->se;
			a.erase(i);
		}
	}
	a[k.fi] += k.se;
}

mll& mg(mll &a, mll &b) {
	if (SZ(a) > SZ(b)) swap(a, b);
	for (auto i : a) b[i.fi] += i.se;
	return b;
}

void DFS(ll now) {
	for (ll to : v[now]) {
		DFS(to);
		dp[now] = mg(dp[now], dp[to]);
	}
	if (w[now]) {
		insert(dp[now], {d[now], w[now]});
	}
	//cout << "NODE::" << now << " " << dp[now] << "\n";
	/*
	for (ll j = 0;j <= t; ++j) {
		dp[now][j] = (j == d[now] ? w[now] : 0);
		for (ll to : v[now]) {
			ll ma = 0;
			for (ll k = 0;k <= j; ++k) {
				ma = max(ma, dp[to][k]);
			}
			dp[now][j] += ma;
		}
	}
	*/
}


int main () {
	ios_base::sync_with_stdio(0);
	cin >> n >> m >> t;
	for (ll i = 2, x;i <= n; ++i) {
		cin >> x;
		v[x].pb(i);
	}
	for (ll i = 0, x;i < m; ++i) {
		cin >> x;
		cin >> d[x] >> w[x];
	}
	DFS(1);
	ll ans = 0;
	for (auto i : dp[1]) {
		ans += i.se;
	}
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

magictree.cpp:2:63: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("unroll-loops, no-stack-protector, Ofast")
      |                                                               ^
magictree.cpp:2:63: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
magictree.cpp:22:42: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   22 | ostream& operator << (ostream& out, mll k) {
      |                                          ^
magictree.cpp:22:42: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:33:26: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   33 | void insert(mll &a, pll k) {
      |                          ^
magictree.cpp:33:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:47:23: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   47 | mll& mg(mll &a, mll &b) {
      |                       ^
magictree.cpp:47:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:53:16: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   53 | void DFS(ll now) {
      |                ^
magictree.cpp:53:16: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:77:11: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   77 | int main () {
      |           ^
magictree.cpp:77:11: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17