oj.uz

Submission #242271

# Submission time Handle Problem Language Result Execution time Memory
242271 2020-06-27T07:56:14 Z shenxy Magic Tree (CEOI19_magictree) C++11
37 / 100
 1284 ms 791416 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: adjlist2[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 18 ms 21248 KB Output is correct
2 Correct 16 ms 21120 KB Output is correct
3 Correct 16 ms 21120 KB Output is correct
4 Correct 15 ms 21120 KB Output is correct
5 Correct 14 ms 21120 KB Output is correct
6 Correct 14 ms 21120 KB Output is correct
7 Correct 14 ms 21120 KB Output is correct
8 Correct 15 ms 21120 KB Output is correct
9 Correct 16 ms 21120 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2688 KB Output is correct
2 Correct 27 ms 2688 KB Output is correct
3 Correct 54 ms 2808 KB Output is correct
4 Correct 51 ms 2808 KB Output is correct
5 Correct 53 ms 2688 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 786400 KB Output is correct
2 Correct 389 ms 786424 KB Output is correct
3 Incorrect 384 ms 786552 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 98 ms 22648 KB Output is correct
2 Correct 94 ms 22776 KB Output is correct
3 Correct 90 ms 26744 KB Output is correct
4 Correct 64 ms 21616 KB Output is correct
5 Correct 75 ms 31992 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21248 KB Output is correct
2 Correct 16 ms 21120 KB Output is correct
3 Correct 16 ms 21120 KB Output is correct
4 Correct 15 ms 21120 KB Output is correct
5 Correct 14 ms 21120 KB Output is correct
6 Correct 14 ms 21120 KB Output is correct
7 Correct 14 ms 21120 KB Output is correct
8 Correct 15 ms 21120 KB Output is correct
9 Correct 16 ms 21120 KB Output is correct
10 Correct 124 ms 22776 KB Output is correct
11 Correct 103 ms 22744 KB Output is correct
12 Correct 105 ms 26744 KB Output is correct
13 Correct 100 ms 21612 KB Output is correct
14 Correct 92 ms 31992 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1284 ms 791416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21248 KB Output is correct
2 Correct 16 ms 21120 KB Output is correct
3 Correct 16 ms 21120 KB Output is correct
4 Correct 15 ms 21120 KB Output is correct
5 Correct 14 ms 21120 KB Output is correct
6 Correct 14 ms 21120 KB Output is correct
7 Correct 14 ms 21120 KB Output is correct
8 Correct 15 ms 21120 KB Output is correct
9 Correct 16 ms 21120 KB Output is correct
10 Correct 398 ms 786400 KB Output is correct
11 Correct 389 ms 786424 KB Output is correct
12 Incorrect 384 ms 786552 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21248 KB Output is correct
2 Correct 16 ms 21120 KB Output is correct
3 Correct 16 ms 21120 KB Output is correct
4 Correct 15 ms 21120 KB Output is correct
5 Correct 14 ms 21120 KB Output is correct
6 Correct 14 ms 21120 KB Output is correct
7 Correct 14 ms 21120 KB Output is correct
8 Correct 15 ms 21120 KB Output is correct
9 Correct 16 ms 21120 KB Output is correct
10 Correct 29 ms 2688 KB Output is correct
11 Correct 27 ms 2688 KB Output is correct
12 Correct 54 ms 2808 KB Output is correct
13 Correct 51 ms 2808 KB Output is correct
14 Correct 53 ms 2688 KB Output is correct
15 Correct 398 ms 786400 KB Output is correct
16 Correct 389 ms 786424 KB Output is correct
17 Incorrect 384 ms 786552 KB Output isn't correct
18 Halted 0 ms 0 KB -