oj.uz

답안 #494926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494926 2021-12-17T15:00:41 Z YJU Magic Tree (CEOI19_magictree) C++14
0 / 100
 872 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 = 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);i != a.end(); i = a.lwb(i->fi+1)) {
		if (i->se > last) {
			i->se -= last;
		} 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:46:23: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   46 | mll& mg(mll &a, mll &b) {
      |                       ^
magictree.cpp:46:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:52:16: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   52 | void DFS(ll now) {
      |                ^
magictree.cpp:52:16: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:76:11: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   76 | int main () {
      |           ^
magictree.cpp:76:11: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 70668 KB Output is correct
2 Incorrect 34 ms 70732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 222048 KB Output is correct
2 Runtime error 872 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 70988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 85936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 70668 KB Output is correct
2 Incorrect 34 ms 70732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 73612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 70668 KB Output is correct
2 Incorrect 34 ms 70732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 70668 KB Output is correct
2 Incorrect 34 ms 70732 KB Output isn't correct
3 Halted 0 ms 0 KB -