답안 #825185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
825185 2023-08-14T15:17:39 Z NK_ Magic Tree (CEOI19_magictree) C++17
47 / 100
2000 ms 29704 KB
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using ll = long long;
using vl = V<ll>;

using T = map<int, ll>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M, K; cin >> N >> M >> K;

	V<vi> chd(N); for(int u = 1; u < N; u++) {
		int p; cin >> p; --p;
		chd[p].pb(u);
	}

	vi W(N, 0), D(N, -1);

	for(int i = 0; i < M; i++) {
		int v, d, w; cin >> v >> d >> w; --v, --d;
		D[v] = d, W[v] = w;
	}
	
	function<T(int)> dfs = [&](int u) {
		T R;
		for(auto& v : chd[u]) {
			T r = dfs(v);
			for(auto p : r) R[p.first] += p.second;
		}		

		if (D[u] != -1) {
			R[D[u]] += W[u];
			ll amt = 0;
			while(1) {
				auto it = R.upper_bound(D[u]);
				if (it == end(R)) break;

				amt += it->s;
				if (W[u] < amt) { it->s = amt - W[u]; break; }
				else R.erase(it);
			}
		}

		return R;
	};

	T ans = dfs(0);
	ll ANS = 0;
	for(auto p : ans) ANS += p.second;
	cout << ANS << nl;
    return 0;
}			

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 7900 KB Output is correct
2 Execution timed out 2068 ms 15720 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 9 ms 580 KB Output is correct
4 Correct 59 ms 28832 KB Output is correct
5 Execution timed out 2078 ms 29704 KB Time limit exceeded
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 7180 KB Output is correct
2 Correct 37 ms 7124 KB Output is correct
3 Correct 40 ms 16232 KB Output is correct
4 Correct 26 ms 5636 KB Output is correct
5 Correct 48 ms 28964 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 43 ms 6476 KB Output is correct
11 Correct 40 ms 6404 KB Output is correct
12 Correct 111 ms 15536 KB Output is correct
13 Correct 24 ms 5000 KB Output is correct
14 Correct 103 ms 28332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1332 KB Output is correct
2 Correct 16 ms 5684 KB Output is correct
3 Correct 16 ms 5716 KB Output is correct
4 Correct 18 ms 5716 KB Output is correct
5 Correct 8 ms 4164 KB Output is correct
6 Correct 193 ms 9496 KB Output is correct
7 Correct 203 ms 14832 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 584 KB Output is correct
12 Correct 9 ms 580 KB Output is correct
13 Correct 59 ms 28832 KB Output is correct
14 Execution timed out 2078 ms 29704 KB Time limit exceeded
15 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 45 ms 7900 KB Output is correct
11 Execution timed out 2068 ms 15720 KB Time limit exceeded
12 Halted 0 ms 0 KB -