oj.uz

Submission #242266

# Submission time Handle Problem Language Result Execution time Memory
242266 2020-06-27T07:54:16 Z shenxy Magic Tree (CEOI19_magictree) C++11
37 / 100
 1183 ms 1048576 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
typedef pair<int, int> ii;
int n, m, k, d[100000];
long long dpt1[100000][22], w[100000];
vector<int> adjlist[100000];
long long dp1(int v, int x) {
	if (dpt1[v][x] != -1) return dpt1[v][x];
	if (x == 0) return dpt1[v][x] = 0;
	dpt1[v][x] = (d[v] == x ? w[v] : 0);
	for (int i: adjlist[v]) dpt1[v][x] += dp1(i, x);
	return dpt1[v][x] = max(dpt1[v][x], dp1(v, x - 1));
}
int cnt = 1;
map<int, ii> mp;
vector<int> adjlist2[1001];
void dfs(int v, int p) {
	d[0] = w[0] = 0;
	if (mp.find(v) != mp.end()) {
		d[cnt] = mp[v].first;
		w[cnt] = mp[v].second;
		adjlist2[p].push_back(cnt);
		p = cnt;
		++cnt;
	}
	for (int i: adjlist[v]) dfs(i, p);
}
long long dpt2[1001][100002];
long long dp2(int v, int x) {
	if (dpt2[v][x] != -1) return dpt2[v][x];
	if (x == 0) return dpt2[v][x] = 0;
	dpt2[v][x] = (d[v] == x ? w[v] : 0);
	for (int i: adjlist[v]) dpt2[v][x] += dp2(i, x);
	return dpt2[v][x] = max(dpt2[v][x], dp2(v, x - 1));
}
int main() {
	scanf("%d %d %d", &n, &m, &k);
	if (k <= 20) {
		int p, v, D, W;
		for (int i = 1; i < n; ++i) {
			scanf("%d", &p);
			adjlist[p - 1].push_back(i);
		}
		fill_n(d, 100000, 0);
		fill_n(w, 100000, 0);
		for (int i = 0; i < m; ++i) {
			scanf("%d %d %d", &v, &D, &W);
			d[v - 1] = D;
			w[v - 1] = W;
		}
		memset(dpt1, -1, sizeof dpt1);
		printf("%lld", dp1(0, k + 1));
	} else if (m <= 1000) {
		int p, v, d, w;
		for (int i = 1; i < n; ++i) {
			scanf("%d", &p);
			adjlist[p - 1].push_back(i);
		}
		for (int i = 0; i < m; ++i) {
			scanf("%d %d %d", &v, &d, &w);
			mp[v] = ii(d, w);
		}
		memset(dpt2, -1, sizeof dpt2);
		dfs(0, 0);
		printf("%lld", dp2(0, k + 1));
	} else {
		for (int i = 1; i < n; ++i) scanf("%d", &k);
		int v, d, w;
		long long ans = 0;
		for (int i = 0; i < m; ++i) {
			scanf("%d %d %d", &v, &d, &w);
			ans += w;
		}
		printf("%lld", ans);
	}
	return 0;
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:45:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
magictree.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &v, &D, &W);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
magictree.cpp:64:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &v, &d, &w);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:71:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i < n; ++i) scanf("%d", &k);
                               ~~~~~^~~~~~~~~~
magictree.cpp:75:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &v, &d, &w);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2688 KB Output is correct
2 Correct 27 ms 3712 KB Output is correct
3 Correct 59 ms 5112 KB Output is correct
4 Correct 52 ms 4856 KB Output is correct
5 Correct 56 ms 5116 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 786552 KB Output is correct
2 Correct 414 ms 786572 KB Output is correct
3 Incorrect 399 ms 786584 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 22776 KB Output is correct
2 Correct 98 ms 22644 KB Output is correct
3 Correct 86 ms 26744 KB Output is correct
4 Correct 63 ms 21616 KB Output is correct
5 Correct 76 ms 31992 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21120 KB Output is correct
2 Correct 15 ms 21120 KB Output is correct
3 Correct 16 ms 21120 KB Output is correct
4 Correct 16 ms 21120 KB Output is correct
5 Correct 17 ms 21120 KB Output is correct
6 Correct 15 ms 21120 KB Output is correct
7 Correct 16 ms 21120 KB Output is correct
8 Correct 15 ms 21120 KB Output is correct
9 Correct 15 ms 21120 KB Output is correct
10 Correct 120 ms 22648 KB Output is correct
11 Correct 100 ms 22732 KB Output is correct
12 Correct 111 ms 26744 KB Output is correct
13 Correct 98 ms 21616 KB Output is correct
14 Correct 90 ms 31992 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1183 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21120 KB Output is correct
2 Correct 15 ms 21120 KB Output is correct
3 Correct 16 ms 21120 KB Output is correct
4 Correct 16 ms 21120 KB Output is correct
5 Correct 17 ms 21120 KB Output is correct
6 Correct 15 ms 21120 KB Output is correct
7 Correct 16 ms 21120 KB Output is correct
8 Correct 15 ms 21120 KB Output is correct
9 Correct 15 ms 21120 KB Output is correct
10 Correct 400 ms 786552 KB Output is correct
11 Correct 414 ms 786572 KB Output is correct
12 Incorrect 399 ms 786584 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21120 KB Output is correct
2 Correct 15 ms 21120 KB Output is correct
3 Correct 16 ms 21120 KB Output is correct
4 Correct 16 ms 21120 KB Output is correct
5 Correct 17 ms 21120 KB Output is correct
6 Correct 15 ms 21120 KB Output is correct
7 Correct 16 ms 21120 KB Output is correct
8 Correct 15 ms 21120 KB Output is correct
9 Correct 15 ms 21120 KB Output is correct
10 Correct 30 ms 2688 KB Output is correct
11 Correct 27 ms 3712 KB Output is correct
12 Correct 59 ms 5112 KB Output is correct
13 Correct 52 ms 4856 KB Output is correct
14 Correct 56 ms 5116 KB Output is correct
15 Correct 400 ms 786552 KB Output is correct
16 Correct 414 ms 786572 KB Output is correct
17 Incorrect 399 ms 786584 KB Output isn't correct
18 Halted 0 ms 0 KB -