QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#599835#2002. RaceModyKachef9 770ms132664kbC++111.7kb2024-09-29 11:48:422024-09-29 11:48:42

Judging History

你现在查看的是最新测评结果

  • [2024-09-29 11:48:42]
  • 评测
  • 测评结果：9
  • 用时：770ms
  • 内存：132664kb
查看
  • [2024-09-29 11:48:42]
  • 提交

answer

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

vector<vector<array<int , 2>>> adj; 
int dp[(int)2e5+1][101][3];
int k ; 

void dfs1(int node  ,  int par){
  for (auto &[i , w] : adj[node]){
    if (i == par) continue;    
    dfs1(i , node); 
    for (int j = 0 ; j <= k ; j++){
      if (j >= w) {
          if (dp[i][j-w][0] + 1 <= dp[node][j][0]) {
            dp[node][j][1] = dp[node][j][0];
            dp[node][j][0] = dp[i][j-w][0] + 1; 
          } 
          else if (dp[i][j-w][0] + 1 <= dp[node][j][1]){
            dp[node][j][1] = dp[i][j-w][0] + 1; 
          }
      }
    }
  }
}

void dfs2(int node , int par){
  for (auto &[i , w] : adj[node]){
    if (i == par) continue;
    for (int j = 0 ; j <= k ; j++){
      dp[i][j][2] = min(dp[i][j][2] , dp[i][j][0]); 
      if (j >= w) {
        int odp = (j >= 2*w && dp[node][j-w][2] == dp[i][j-2*w][0] + 1 ? dp[node][j-w][1] : dp[node][j-w][2]); 
        dp[i][j][2] = min(dp[i][j][2] , odp + 1); 
      }
    }
    dfs2(i , node); 
  }
}



signed best_path(signed N, signed K, signed H[][2], signed L[])
{
  
  adj.assign(N , {}); 
  k = K; 
  for (int i = 0 ; i < N-1 ; i++){
    adj[H[i][0]].push_back({H[i][1] , L[i]});
    adj[H[i][1]].push_back({H[i][0] , L[i]}); 
  }
  for (int i = 0 ; i <= N ; i++){
    for (int j = 1  ; j <= K; j++) {
      for (int l = 0 ; l < 3 ; l++){
        dp[i][j][l] = 1e9; 
      }
    }
  }
  dfs1(0 , -1);
  for (int j = 0 ; j <= K; j++) dp[0][j][2] = dp[0][j][0]; 
  dfs2(0 , -1); 
  int ans = 1e9; 
  for (int i = 0 ; i < N ; i++){
    ans = min(ans , dp[i][k][2]); 
  }
  return (ans == 1e9 ? -1 : ans);
}
源文件, 语言: C++11

详细

Subtask #1:

score: 9
Accepted

Test #1:

score: 9
Accepted
time: 1ms
memory: 7832kb

input:

100 50
0 1 1
1 2 2
2 3 2
3 4 1
4 5 2
5 6 1
6 7 1
7 8 1
8 9 1
9 10 2
10 11 2
11 12 2
12 13 1
13 14 1
14 15 1
15 16 2
16 17 1
17 18 2
18 19 1
19 20 1
20 21 1
21 22 2
22 23 2
23 24 2
24 25 2
25 26 1
26 27 2
27 28 2
28 29 2
29 30 2
30 31 2
31 32 1
32 33 1
33 34 2
34 35 2
35 36 1
36 37 1
37 38 1
38 39 1
...

output:

Correct.

Test #2:

score: 9
Accepted
time: 1ms
memory: 8132kb

input:

100 100
0 1 39
1 2 26
2 3 27
3 4 43
4 5 18
5 6 25
6 7 29
7 8 32
8 9 32
9 10 9
10 11 10
11 12 1
12 13 38
13 14 26
14 15 12
15 16 11
16 17 19
17 18 34
18 19 19
19 20 8
20 21 42
21 22 15
22 23 21
23 24 13
24 25 24
25 26 18
26 27 45
27 28 5
28 29 12
29 30 11
30 31 2
31 32 31
32 33 31
33 34 50
34 35 7
35...

output:

Correct.

Test #3:

score: 9
Accepted
time: 0ms
memory: 7844kb

input:

100 100
0 1 48
1 2 1
2 3 42
3 4 37
4 5 29
5 6 35
6 7 49
7 8 26
8 9 11
9 10 4
10 11 3
11 12 46
12 13 42
13 14 35
14 15 42
15 16 16
16 17 9
17 18 49
18 19 4
19 20 15
20 21 40
21 22 0
22 23 21
23 24 40
24 25 49
25 26 6
26 27 2
27 28 19
28 29 35
29 30 39
30 31 15
31 32 16
32 33 40
33 34 44
34 35 36
35 3...

output:

Correct.

Test #4:

score: 9
Accepted
time: 0ms
memory: 7840kb

input:

100 100
0 1 27
1 2 28
2 3 0
3 4 18
4 5 40
5 6 12
6 7 6
7 8 29
8 9 37
9 10 39
10 11 6
11 12 32
12 13 34
13 14 30
14 15 39
15 16 39
16 17 46
17 18 23
18 19 43
19 20 47
20 21 46
21 22 34
22 23 31
23 24 28
24 25 12
25 26 13
26 27 19
27 28 25
28 29 44
29 30 25
30 31 9
31 32 29
32 33 11
33 34 45
34 35 30
...

output:

Correct.

Test #5:

score: 9
Accepted
time: 1ms
memory: 8144kb

input:

100 100
0 1 1
1 2 2
2 3 2
3 4 3
4 5 3
5 6 3
6 7 0
7 8 3
8 9 3
9 10 3
10 11 0
11 12 2
12 13 2
13 14 3
14 15 2
15 16 3
16 17 2
17 18 1
18 19 0
19 20 1
20 21 2
21 22 2
22 23 2
23 24 1
24 25 1
25 26 3
26 27 1
27 28 3
28 29 2
29 30 3
30 31 1
31 32 0
32 33 3
33 34 1
34 35 3
35 36 1
36 37 3
37 38 3
38 39 1...

output:

Correct.

Test #6:

score: 9
Accepted
time: 1ms
memory: 7932kb

input:

100 100
0 1 4
1 2 3
2 3 5
3 4 0
4 5 5
5 6 4
6 7 2
7 8 1
8 9 5
9 10 5
10 11 3
11 12 1
12 13 3
13 14 4
14 15 3
15 16 1
16 17 4
17 18 1
18 19 5
19 20 0
20 21 1
21 22 1
22 23 5
23 24 1
24 25 4
25 26 5
26 27 5
27 28 2
28 29 4
29 30 0
30 31 0
31 32 4
32 33 3
33 34 5
34 35 2
35 36 5
36 37 4
37 38 5
38 39 4...

output:

Correct.

Test #7:

score: 9
Accepted
time: 1ms
memory: 5792kb

input:

100 100
0 1 2
1 2 0
2 3 1
3 4 0
4 5 0
5 6 0
6 7 2
7 8 1
8 9 2
9 10 0
10 11 2
11 12 0
12 13 0
13 14 1
14 15 1
15 16 2
16 17 2
17 18 1
18 19 2
19 20 2
20 21 1
21 22 2
22 23 0
23 24 0
24 25 2
25 26 1
26 27 0
27 28 2
28 29 1
29 30 2
30 31 2
31 32 1
32 33 0
33 34 1
34 35 0
35 36 2
36 37 0
37 38 2
38 39 0...

output:

Correct.

Test #8:

score: 9
Accepted
time: 1ms
memory: 7820kb

input:

100 100
0 1 2
1 2 3
2 3 2
3 4 0
4 5 2
5 6 1
6 7 2
7 8 1
8 9 2
9 10 1
10 11 2
11 12 2
12 13 0
13 14 3
14 15 0
15 16 3
16 17 3
17 18 0
18 19 2
19 20 0
20 21 3
21 22 1
22 23 0
23 24 3
24 25 3
25 26 0
26 27 1
27 28 1
28 29 0
29 30 2
30 31 3
31 32 3
32 33 2
33 34 0
34 35 3
35 36 2
36 37 3
37 38 1
38 39 2...

output:

Correct.

Test #9:

score: 9
Accepted
time: 1ms
memory: 9772kb

input:

100 100
0 1 3
1 2 0
2 3 1
3 4 3
4 5 2
5 6 0
6 7 3
7 8 3
8 9 2
9 10 3
10 11 2
11 12 3
12 13 3
13 14 3
14 15 1
15 16 1
16 17 1
17 18 0
18 19 0
19 20 0
20 21 0
21 22 2
22 23 0
23 24 0
24 25 0
25 26 2
26 27 0
27 28 3
28 29 3
29 30 0
30 31 0
31 32 2
32 33 0
33 34 0
34 35 3
35 36 2
36 37 0
37 38 0
38 39 2...

output:

Correct.

Test #10:

score: 9
Accepted
time: 0ms
memory: 7832kb

input:

100 100
0 1 0
1 2 3
2 3 1
3 4 3
4 5 1
5 6 1
6 7 0
7 8 0
8 9 0
9 10 2
10 11 1
11 12 1
12 13 0
13 14 2
14 15 0
15 16 1
16 17 1
17 18 2
18 19 0
19 20 3
20 21 2
21 22 2
22 23 0
23 24 0
24 25 3
25 26 1
26 27 2
27 28 3
28 29 0
29 30 3
30 31 3
31 32 2
32 33 1
33 34 3
34 35 3
35 36 2
36 37 0
37 38 2
38 39 1...

output:

Correct.

Test #11:

score: 9
Accepted
time: 1ms
memory: 7864kb

input:

100 90
0 1 7
1 2 7
2 3 8
3 4 8
4 5 7
5 6 8
6 7 7
7 8 7
8 9 7
9 10 7
10 11 8
11 12 8
12 13 7
13 14 7
14 15 7
15 16 8
16 17 7
17 18 7
18 19 8
19 20 8
20 21 8
21 22 7
22 23 8
23 24 8
24 25 8
25 26 8
26 27 8
27 28 7
28 29 7
29 30 7
30 31 7
31 32 7
32 33 7
33 34 8
34 35 7
35 36 8
36 37 7
37 38 7
38 39 8
...

output:

Correct.

Test #12:

score: 9
Accepted
time: 1ms
memory: 8124kb

input:

100 78
0 1 18
1 2 19
2 3 17
3 4 15
4 5 16
5 6 15
6 7 19
7 8 17
8 9 15
9 10 15
10 11 17
11 12 18
12 13 19
13 14 16
14 15 17
15 16 18
16 17 17
17 18 15
18 19 19
19 20 19
20 21 17
21 22 18
22 23 19
23 24 16
24 25 17
25 26 19
26 27 17
27 28 17
28 29 19
29 30 15
30 31 16
31 32 16
32 33 18
33 34 15
34 35 ...

output:

Correct.

Test #13:

score: 9
Accepted
time: 0ms
memory: 8128kb

input:

100 100
1 0 0
2 1 0
3 2 0
4 3 0
5 4 0
6 5 0
7 6 0
8 7 0
9 8 0
10 9 0
11 10 0
12 11 0
13 12 0
14 13 0
15 14 0
16 15 0
17 16 0
18 17 0
19 18 0
20 19 0
21 20 0
22 21 0
23 22 0
24 23 0
25 24 0
26 25 0
27 26 0
28 27 0
29 28 0
30 29 0
31 30 0
32 31 0
33 32 0
34 33 0
35 34 0
36 35 0
37 36 0
38 37 0
39 38 0...

output:

Correct.

Test #14:

score: 9
Accepted
time: 1ms
memory: 7840kb

input:

100 100
1 0 1000000
2 1 1000000
3 2 1000000
4 3 1000000
5 4 1000000
6 5 1000000
7 6 1000000
8 7 1000000
9 8 1000000
10 9 1000000
11 10 1000000
12 11 1000000
13 12 1000000
14 13 1000000
15 14 1000000
16 15 1000000
17 16 1000000
18 17 1000000
19 18 1000000
20 19 1000000
21 20 1000000
22 21 1000000
23 ...

output:

Correct.

Test #15:

score: 9
Accepted
time: 1ms
memory: 7892kb

input:

100 100
0 1 1
1 2 1
2 3 0
3 4 0
4 5 1
5 6 1
6 7 0
7 8 1
8 9 0
9 10 1
10 11 1
11 12 0
12 13 0
13 14 0
14 15 1
15 16 1
16 17 0
17 18 1
18 19 1
19 20 0
20 21 0
21 22 0
22 23 1
23 24 0
24 25 0
25 26 0
26 27 1
27 28 0
28 29 1
29 30 0
30 31 1
31 32 0
32 33 1
33 34 0
34 35 0
35 36 1
36 37 1
37 38 1
38 39 1...

output:

Correct.

Test #16:

score: 9
Accepted
time: 1ms
memory: 7932kb

input:

100 100
0 1 101
1 2 85
2 3 68
3 4 25
4 5 87
5 6 30
6 7 87
7 8 37
8 9 14
9 10 18
10 11 4
11 12 36
12 13 27
13 14 101
14 15 80
15 16 29
16 17 7
17 18 8
18 19 31
19 20 51
20 21 0
21 22 22
22 23 40
23 24 28
24 25 7
25 26 48
26 27 74
27 28 20
28 29 59
29 30 23
30 31 34
31 32 75
32 33 48
33 34 19
34 35 85...

output:

Correct.

Test #17:

score: 9
Accepted
time: 1ms
memory: 7780kb

input:

100 100
0 1 90
1 2 38
2 3 31
3 4 72
4 5 4
5 6 36
6 7 45
7 8 23
8 9 73
9 10 92
10 11 71
11 12 5
12 13 26
13 14 92
14 15 35
15 16 86
16 17 2
17 18 3
18 19 53
19 20 82
20 21 17
21 22 58
22 23 7
23 24 89
24 25 84
25 26 8
26 27 96
27 28 9
28 29 24
29 30 48
30 31 30
31 32 18
32 33 56
33 34 58
34 35 14
35 ...

output:

Correct.

Test #18:

score: 9
Accepted
time: 1ms
memory: 10172kb

input:

100 100
0 1 3
1 2 6
2 3 1
3 4 9
4 5 8
5 6 0
6 7 6
7 8 10
8 9 4
9 10 5
10 11 1
11 12 1
12 13 9
13 14 4
14 15 5
15 16 7
16 17 7
17 18 5
18 19 6
19 20 8
20 21 1
21 22 5
22 23 1
23 24 2
24 25 3
25 26 7
26 27 8
27 28 3
28 29 9
29 30 9
30 31 3
31 32 1
32 33 8
33 34 5
34 35 6
35 36 5
36 37 5
37 38 2
38 39 ...

output:

Correct.

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #19:

score: 12
Accepted
time: 1ms
memory: 7888kb

input:

10 7
5 0 1
2 0 1
8 0 2
9 5 2
3 9 1
1 9 3
4 8 3
7 3 3
6 8 1
3

output:

Correct.

Test #20:

score: 0
Wrong Answer
time: 770ms
memory: 12112kb

input:

1000 199112
762 339 28482
749 762 227
319 749 53263
552 762 12523
716 339 46366
613 319 74345
249 339 72086
42 249 2870
589 552 5725
179 42 53677
760 249 5715
298 552 163
67 179 2902
573 319 2
219 573 10621
539 749 4024
335 219 254
727 42 6119
429 298 8518
825 219 17484
248 249 43205
244 67 11387
31...

output:

Incorrect. Returned 3, Expected 7.

Subtask #3:

score: 0
Memory Limit Exceeded

Test #39:

score: 22
Accepted
time: 150ms
memory: 132664kb

input:

100000 100
1 0 1
2 1 10
3 1 1
4 3 5
5 3 6
6 5 6
7 3 10
8 5 9
9 8 7
10 9 9
11 6 7
12 6 3
13 10 10
14 9 1
15 14 7
16 15 5
17 10 1
18 14 9
19 12 8
20 18 10
21 10 9
22 12 7
23 14 9
24 15 5
25 15 2
26 20 4
27 19 10
28 17 8
29 16 8
30 24 10
31 17 2
32 28 7
33 27 8
34 21 4
35 28 7
36 22 4
37 18 6
38 27 6
3...

output:

Correct.

Test #40:

score: 0
Memory Limit Exceeded

input:

200000 100
192164 110199 93
47882 192164 72
146145 47882 33
126329 146145 51
179411 126329 12
64302 179411 54
149999 64302 60
68743 149999 54
6947 68743 48
34108 6947 96
153071 34108 21
124245 153071 27
80021 124245 78
35586 80021 33
63565 35586 99
146479 63565 78
112365 146479 87
66626 112365 18
16...

output:

Correct.

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

服务器时间: 2024-11-29 19:57:34 | 开源项目