QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#540868	#8938. Crawling on a Tree	ucup-team052^#	WA	2ms	15836kb	C++20	2.4kb	2024-08-31 17:59:54	2024-08-31 17:59:54

Judging History

This is the latest submission verdict.

[2024-08-31 17:59:54]
Judged

Verdict: WA
Time: 2ms
Memory: 15836kb

Show

[2024-08-31 17:59:54]
Submitted

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll INFLL = 1e18;
const int INF = 0x3f3f3f3f;
const int N = 10005;

struct edge {
	int v, l, k;
	edge (int a = 0, int b = 0, int c = 0) : v(a), l(b), k(c) {}
};

vector <edge> adj[N];
int fa[N], l[N], k[N], c[N];
int n, m;

ll f[N][N], tf[N]; // f[u][i] : cost
int g[N][N], tg[N]; // g[u][i] : u eat i turtles, minimum count of turtle
void dfs1(int u) {
	for (int i = 0; i <= m; i++) g[u][i] = f[u][i] = 0;
	for (auto t : adj[u]) {
		int v = t.v;
		if (v == fa[u]) continue;
		fa[v] = u; l[v] = t.l; k[v] = t.k; dfs1(v);
		memset(tg, 0x3f, sizeof(tg));
		for (int i = 0; i <= m; i++) {
			if (g[u][i] == INF) continue;
			for (int j = 0; j <= m - i; j++) {
				if (g[v][j] == INF) continue;
				int ng = max(g[u][i], j + g[v][j]);
				if (ng < tg[i + j]) {
					tf[i + j] = f[u][i] + f[v][j];
					tg[i + j] = ng;
				} else if (ng == tg[i + j]) {
					tf[i + j] = min(tf[i + j], f[u][i] + f[v][j]);
				}
			}
		}
		memcpy(f[u], tf, sizeof(f[u]));
		memcpy(g[u], tg, sizeof(g[u]));
	}
	for (int i = 0; i <= m; i++) {
		if (g[u][i] == INF) continue;
		g[u][i] = max(0, g[u][i] - i);
		g[u][i] = max(g[u][i], c[u] - i);
	}
	for (int i = 0; i < m; i++) {
		if (g[u][i] == INF) continue;
		if (max(0, g[u][i] - 1) < g[u][i + 1]) {
			g[u][i + 1] = g[u][i] - 1;
			f[u][i + 1] = f[u][i];
		} else if (max(0, g[u][i] - 1) == g[u][i + 1]) {
			f[u][i + 1] = min(f[u][i + 1], f[u][i]);
		}
	}
	for (int i = 0; i <= m; i++) {
		if (i + g[u][i] * 2 > k[u]) {
			g[u][i] = INF;
		}
		if (g[u][i] != INF) f[u][i] += 1ll * l[u] * (i + g[u][i] * 2);
		if (g[u][i] != INF) assert(g[u][i] <= m);
	}
}

ll ans[N];

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int u, v, l, k;
		cin >> u >> v >> l >> k;
		adj[u].emplace_back(v, l, k);
		adj[v].emplace_back(u, l, k);
	}
	k[1] = 1e9;
	for (int i = 2; i <= n; i++) cin >> c[i];
	dfs1(1);
	for (int i = 0; i <= m; i++) ans[i] = INFLL;
	for (int i = 0; i <= m; i++) {
		if (g[1][i] != INF && i + g[1][i] <= m) {
			ans[i + g[1][i]] = min(ans[i + g[1][i]], f[1][i]);
		}
	}
	for (int i = 1; i <= m; i++) ans[i] = min(ans[i], ans[i - 1]);
	for (int i = 1; i <= m; i++) {
		if (ans[i] == INFLL) cout << -1 << '\n';
		else cout << ans[i] << '\n';
	}
	return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 5784kb

input:

output:

-1
13

result:

ok 2 number(s): "-1 13"

Test #2:

score: 0

Accepted

time: 1ms

memory: 5832kb

input:

output:

-1
-1

result:

ok 2 number(s): "-1 -1"

Test #3:

score: 0

Accepted

time: 1ms

memory: 5704kb

input:

2 1
2 1 1 1
1

output:

result:

ok 1 number(s): "1"

Test #4:

score: 0

Accepted

time: 1ms

memory: 5800kb

input:

2 50
2 1 1 1
50

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 50 numbers

Test #5:

score: 0

Accepted

time: 1ms

memory: 7892kb

input:

2 50
2 1 1 50
50

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50

result:

ok 50 numbers

Test #6:

score: 0

Accepted

time: 1ms

memory: 5784kb

input:

2 50
1 2 1 100000
50

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50

result:

ok 50 numbers

Test #7:

score: 0

Accepted

time: 0ms

memory: 12304kb

input:

50 1
1 2 85524 58896
2 3 9137 9819
3 4 3036 88987
4 5 78909 15766
5 6 76067 34996
6 7 64247 63701
7 8 14 9384
8 9 37698 35418
9 10 51427 91691
10 11 39818 89351
11 12 47887 64083
12 13 43836 44135
13 14 22561 83803
14 15 52617 97413
15 16 41869 83810
16 17 35783 18642
17 18 5514 34601
18 19 50448 49...

output:

result:

ok 1 number(s): "3202064"

Test #8:

score: 0

Accepted

time: 0ms

memory: 13368kb

input:

50 5
1 2 48897 1
2 3 59967 3
3 4 61806 2
4 5 48519 4
5 6 77213 5
6 7 32384 1
7 8 59009 2
8 9 98263 1
9 10 42945 6
10 11 5549 6
11 12 51097 6
12 13 88536 4
13 14 44215 2
14 15 56896 2
15 16 19263 5
16 17 30787 5
17 18 20135 3
18 19 75922 4
19 20 35387 5
20 21 84081 4
21 22 54235 5
22 23 44411 3
23 24...

output:

-1
-1
-1
-1
-1

result:

ok 5 number(s): "-1 -1 -1 -1 -1"

Test #9:

score: 0

Accepted

time: 2ms

memory: 12696kb

input:

50 10
1 2 44914 14
2 3 84737 11
3 4 76461 7
4 5 36207 14
5 6 48479 10
6 7 88167 14
7 8 71415 7
8 9 95290 10
9 10 12553 7
10 11 2718 7
11 12 89004 12
12 13 86605 10
13 14 76252 14
14 15 75076 10
15 16 52024 14
16 17 23365 15
17 18 93829 13
18 19 3765 10
19 20 72010 9
20 21 17119 7
21 22 83633 14
22 2...

output:

result:

ok 10 numbers

Test #10:

score: 0

Accepted

time: 2ms

memory: 12040kb

input:

50 20
1 2 84157 10
2 3 20072 5
3 4 36547 8
4 5 46072 11
5 6 64560 10
6 7 51220 8
7 8 6257 14
8 9 85793 7
9 10 67400 7
10 11 37948 14
11 12 64361 12
12 13 15316 14
13 14 86110 9
14 15 66507 13
15 16 31139 9
16 17 91577 12
17 18 30027 7
18 19 17865 9
19 20 16377 14
20 21 70649 14
21 22 29703 5
22 23 7...

output:

result:

ok 20 numbers

Test #11:

score: 0

Accepted

time: 2ms

memory: 15836kb

input:

50 30
1 2 92254 8
2 3 67112 8
3 4 51573 12
4 5 45236 11
5 6 86302 12
6 7 5974 14
7 8 96820 7
8 9 83266 13
9 10 83174 8
10 11 14722 9
11 12 80728 10
12 13 71250 12
13 14 59937 14
14 15 33700 7
15 16 58668 9
16 17 66269 9
17 18 30776 9
18 19 91575 11
19 20 51383 7
20 21 92925 14
21 22 70739 7
22 23 60...

output:

result:

ok 30 numbers

Test #12:

score: 0

Accepted

time: 0ms

memory: 13076kb

input:

50 50
1 2 44120 30
2 3 73250 30
3 4 68398 30
4 5 98932 30
5 6 98719 30
6 7 96765 30
7 8 71479 30
8 9 37151 30
9 10 91752 30
10 11 8218 30
11 12 66373 30
12 13 49494 30
13 14 56744 30
14 15 829 30
15 16 61166 30
16 17 64926 30
17 18 76821 30
18 19 18028 30
19 20 3749 30
20 21 38173 30
21 22 57828 30
...

output:

result:

ok 50 numbers

Test #13:

score: 0

Accepted

time: 2ms

memory: 15464kb

input:

50 50
1 2 32039 30
2 3 25573 30
3 4 93435 30
4 5 12864 30
5 6 81011 30
6 7 72386 30
7 8 60555 30
8 9 44065 30
9 10 87410 30
10 11 95846 30
11 12 22377 30
12 13 33453 30
13 14 24010 30
14 15 84584 30
15 16 66399 30
16 17 15580 30
17 18 91590 30
18 19 72162 30
19 20 96308 30
20 21 57991 30
21 22 69903...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 50 numbers

Test #14:

score: -100

Wrong Answer

time: 0ms

memory: 13304kb

input:

50 50
1 2 90182 100
2 3 80679 100
3 4 17341 100
4 5 14788 100
5 6 25843 100
6 7 19327 100
7 8 64668 100
8 9 261 100
9 10 11742 100
10 11 87415 100
11 12 4372 100
12 13 27691 100
13 14 88014 100
14 15 71401 100
15 16 79534 100
16 17 74095 100
17 18 81196 100
18 19 93774 100
19 20 18579 100
20 21 8033...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
127025890

result:

wrong answer 50th numbers differ - expected: '126552274', found: '127025890'