oj.uz

Submission #494931

# Submission time Handle Problem Language Result Execution time Memory
494931 2021-12-17T15:04:57 Z YJU Magic Tree (CEOI19_magictree) C++17
34 / 100
 811 ms 1048580 KB 
#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 = 1e5 + 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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 3 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 3 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 3 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 157728 KB Output is correct
2 Runtime error 811 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7628 KB Output is correct
2 Correct 6 ms 8960 KB Output is correct
3 Correct 18 ms 19964 KB Output is correct
4 Correct 89 ms 58360 KB Output is correct
5 Runtime error 759 ms 1048580 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 20952 KB Output is correct
2 Correct 79 ms 17688 KB Output is correct
3 Correct 71 ms 29184 KB Output is correct
4 Correct 49 ms 23060 KB Output is correct
5 Correct 62 ms 36292 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 3 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 3 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 3 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 124 ms 43204 KB Output is correct
11 Correct 123 ms 34636 KB Output is correct
12 Correct 187 ms 138744 KB Output is correct
13 Correct 182 ms 135744 KB Output is correct
14 Correct 159 ms 141644 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10208 KB Output is correct
2 Correct 38 ms 15064 KB Output is correct
3 Correct 41 ms 14780 KB Output is correct
4 Correct 47 ms 16188 KB Output is correct
5 Runtime error 768 ms 1048580 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 3 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 3 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 3 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 4 ms 7628 KB Output is correct
11 Correct 6 ms 8960 KB Output is correct
12 Correct 18 ms 19964 KB Output is correct
13 Correct 89 ms 58360 KB Output is correct
14 Runtime error 759 ms 1048580 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 3 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 3 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 3 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 226 ms 157728 KB Output is correct
11 Runtime error 811 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -