teratail
回答率
85.45%
質問するログイン新規登録
トップに関する質問Atcoder beginner contest 222 E問題の深さ全探索で求めた最短経路の復元が正しくできない

編集履歴

質問編集履歴

5

誤字

2021/10/10 06:29

投稿

rdld036
rdld036

スコア16

test CHANGED
File without changes
test CHANGED
@@ -100,7 +100,7 @@
100
100
 
101
101
  }
102
102
 
103
-
103
+
104
104
 
105
105
 
106
106
 
@@ -120,13 +120,13 @@
120
120
 
121
121
  int edge_id = G[cur][prev_v[cur]].second;
122
122
 
123
- 　　　　　　 cout << "cur = " << cur << " edge id = " << edge_id << '\n';
123
+ cout << "cur = " << cur << " edge id = " << edge_id << '\n';
124
124
 
125
125
  C[edge_id]++;
126
126
 
127
127
  cur = prev_v[cur];
128
128
 
129
-
129
+
130
130
 
131
131
  }
132
132
 
@@ -174,8 +174,6 @@
174
174
 
175
175
  }
176
176
 
177
-
178
-
179
177
  ```
180
178
 
181
179
 

4

５時

2021/10/10 06:29

投稿

rdld036
rdld036

スコア16

test CHANGED
File without changes
test CHANGED
@@ -120,7 +120,7 @@
120
120
 
121
121
  int edge_id = G[cur][prev_v[cur]].second;
122
122
 
123
- 　　　　　　 cout << "cur = " << cur << " edge id = " << edge_path_id << '\n';
123
+ 　　　　　　 cout << "cur = " << cur << " edge id = " << edge_id << '\n';
124
124
 
125
125
  C[edge_id]++;
126
126
 

3

書式の改善

2021/10/10 06:27

投稿

rdld036
rdld036

スコア16

test CHANGED
File without changes
test CHANGED
@@ -120,6 +120,8 @@
120
120
 
121
121
  int edge_id = G[cur][prev_v[cur]].second;
122
122
 
123
+ 　　　　　　 cout << "cur = " << cur << " edge id = " << edge_path_id << '\n';
124
+
123
125
  C[edge_id]++;
124
126
 
125
127
  cur = prev_v[cur];

2

文法の訂正

2021/10/10 06:23

投稿

rdld036
rdld036

スコア16

test CHANGED
File without changes
test CHANGED
@@ -208,7 +208,7 @@
208
208
 
209
209
  cur = 1 edge id = 0
210
210
 
211
- このサンプルケースではどの辺も一回ずつしか通らないはず。これによって、このあとのdpで使う配列が正しく作ることができない。
211
+ このサンプルケースではどの辺も一回ずつしか通らないはず。これによって、このあとのdpで使う配列Cを正しく作ることができない。
212
212
 
213
213
  ### 補足情報（FW/ツールのバージョンなど）
214
214
 

1

文法の訂正

2021/10/10 06:21

投稿

rdld036
rdld036

スコア16

test CHANGED
@@ -1 +1 @@
1
- Atcoder beginner contest 222 E問題の深さ全探索で求めた最短経路の復元が機能しない
1
+ Atcoder beginner contest 222 E問題の深さ全探索で求めた最短経路の復元が正しくできない
test CHANGED
@@ -2,188 +2,180 @@
2
2
 
3
3
  ABC222の[E問題](https://atcoder.jp/contests/abc222/tasks/abc222_e)を以下のコードで解いたのですが、すべてACになりません。また、自分の実行環境とAtcoderのコードテストで動かした結果が同じサンプル入力を使っているにもかかわらず、一致しません。汚いコードで申し訳ないのですが、原因を教えていただけると幸いです。
4
4
 
5
- ■■な機能を実装中に以下のエラーメッセージが発生しました。
5
+
6
-
7
-
8
-
6
+
7
+
8
+
9
+
10
+
11
+
12
+
9
- ### 発生している問題・エラーメッセージ
13
+ ### 該当のソースコード
14
+
15
+
16
+
17
+ ```C++
18
+
19
+ #include <bits/stdc++.h>
20
+
21
+ using namespace std;
22
+
23
+ typedef long long ll;
24
+
25
+ typedef long double ld;
26
+
27
+ const int INF = 1e9;
28
+
29
+
30
+
31
+ template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
32
+
33
+ template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
34
+
35
+ template <typename Type> inline string toString(const Type &a){ostringstream oss; oss << a; return oss.str();}
36
+
37
+
38
+
39
+ int N, M, K;
40
+
41
+ const int mod = 998244353;
42
+
43
+ vector<int> A, C, prev_v;
44
+
45
+ vector<vector<pair<int, int>>> G;
46
+
47
+ vector<vector<ll>> dp;
48
+
49
+
50
+
51
+ // first... target, second... edge id
52
+
53
+ void dfs(int v, int goal){
54
+
55
+ if(v == goal) return;
56
+
57
+ for(pair<int, int> nv : G[v]){
58
+
59
+ if(prev_v[nv.first] == -1 || prev_v[nv.first] != INF || nv.first == prev_v[v]) continue;
60
+
61
+ prev_v[nv.first] = v;
62
+
63
+ dfs(nv.first, goal);
64
+
65
+ }
66
+
67
+ }
68
+
69
+
70
+
71
+ int main(){
72
+
73
+ ios::sync_with_stdio(false);
74
+
75
+ cin.tie(0);
76
+
77
+ cin >> N >> M >> K;
78
+
79
+ A.resize(M);
80
+
81
+ G.resize(N);
82
+
83
+ for(int i = 0; i < M; ++i){
84
+
85
+ cin >> A[i];
86
+
87
+ A[i]--;
88
+
89
+ }
90
+
91
+ for(int i = 0; i < N - 1; ++i){
92
+
93
+ int a, b;
94
+
95
+ cin >> a >> b;
96
+
97
+ a--; b--;
98
+
99
+ G[a].push_back(make_pair(b, i)); G[b].push_back(make_pair(a, i));
100
+
101
+ }
102
+
103
+
104
+
105
+
106
+
107
+ C.assign(N - 1, 0);
108
+
109
+ for(int i = 0; i < M - 1; ++i){
110
+
111
+ prev_v.assign(N, INF);
112
+
113
+ prev_v[A[i]] = -1;
114
+
115
+ dfs(A[i], A[i + 1]);
116
+
117
+ int cur = A[i + 1];
118
+
119
+ while(cur != A[i]){
120
+
121
+ int edge_id = G[cur][prev_v[cur]].second;
122
+
123
+ C[edge_id]++;
124
+
125
+ cur = prev_v[cur];
126
+
127
+
128
+
129
+ }
130
+
131
+ }
132
+
133
+ ll sumC = 0;
134
+
135
+ for(int i = 0; i < N - 1; ++i) sumC += C[i];
136
+
137
+ if((K + sumC) % 2 == 1 || K + sumC < 0){
138
+
139
+ cout << 0 << endl;
140
+
141
+ return 0;
142
+
143
+ }
144
+
145
+ dp.assign(N, vector<ll>((K + sumC) / 2 + 1 , 0));
146
+
147
+ dp[0][0] = 1;
148
+
149
+ for(int i = 0; i < N - 1; ++i){
150
+
151
+ for(int j = 0; j <= (K + sumC) / 2; ++j){
152
+
153
+ if(C[i] <= j){
154
+
155
+ dp[i + 1][j] += dp[i][j - C[i]];
156
+
157
+ dp[i + 1][j] %= mod;
158
+
159
+ }
160
+
161
+ dp[i + 1][j] += dp[i][j];
162
+
163
+ dp[i + 1][j] %= mod;
164
+
165
+ }
166
+
167
+ }
168
+
169
+
170
+
171
+ cout << dp[N - 1][(K + sumC) / 2] << endl;
172
+
173
+ }
10
174
 
11
175
 
12
176
 
13
177
  ```
14
178
 
15
- エラーメッセージ
16
-
17
- ```
18
-
19
-
20
-
21
- ### 該当のソースコード
22
-
23
-
24
-
25
- ```C++
26
-
27
- #include <bits/stdc++.h>
28
-
29
- using namespace std;
30
-
31
- typedef long long ll;
32
-
33
- typedef long double ld;
34
-
35
- const int INF = 1e9;
36
-
37
-
38
-
39
- template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
40
-
41
- template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
42
-
43
- template <typename Type> inline string toString(const Type &a){ostringstream oss; oss << a; return oss.str();}
44
-
45
-
46
-
47
- int N, M, K;
48
-
49
- const int mod = 998244353;
50
-
51
- vector<int> A, C, prev_v;
52
-
53
- vector<vector<pair<int, int>>> G;
54
-
55
- vector<vector<ll>> dp;
56
-
57
-
58
-
59
- // first... target, second... edge id
60
-
61
- void dfs(int v, int goal){
62
-
63
- if(v == goal) return;
64
-
65
- for(pair<int, int> nv : G[v]){
66
-
67
- if(prev_v[nv.first] == -1 || prev_v[nv.first] != INF || nv.first == prev_v[v]) continue;
68
-
69
- prev_v[nv.first] = v;
70
-
71
- dfs(nv.first, goal);
72
-
73
- }
74
-
75
- }
76
-
77
-
78
-
79
- int main(){
80
-
81
- ios::sync_with_stdio(false);
82
-
83
- cin.tie(0);
84
-
85
- cin >> N >> M >> K;
86
-
87
- A.resize(M);
88
-
89
- G.resize(N);
90
-
91
- for(int i = 0; i < M; ++i){
92
-
93
- cin >> A[i];
94
-
95
- A[i]--;
96
-
97
- }
98
-
99
- for(int i = 0; i < N - 1; ++i){
100
-
101
- int a, b;
102
-
103
- cin >> a >> b;
104
-
105
- a--; b--;
106
-
107
- G[a].push_back(make_pair(b, i)); G[b].push_back(make_pair(a, i));
108
-
109
- }
110
-
111
-
112
-
113
-
114
-
115
- C.assign(N - 1, 0);
116
-
117
- for(int i = 0; i < M - 1; ++i){
118
-
119
- prev_v.assign(N, INF);
120
-
121
- prev_v[A[i]] = -1;
122
-
123
- dfs(A[i], A[i + 1]);
124
-
125
- int cur = A[i + 1];
126
-
127
- while(cur != A[i]){
128
-
129
- int edge_id = G[cur][prev_v[cur]].second;
130
-
131
- C[edge_id]++;
132
-
133
- cur = prev_v[cur];
134
-
135
-
136
-
137
- }
138
-
139
- }
140
-
141
- ll sumC = 0;
142
-
143
- for(int i = 0; i < N - 1; ++i) sumC += C[i];
144
-
145
- if((K + sumC) % 2 == 1 || K + sumC < 0){
146
-
147
- cout << 0 << endl;
148
-
149
- return 0;
150
-
151
- }
152
-
153
- dp.assign(N, vector<ll>((K + sumC) / 2 + 1 , 0));
154
-
155
- dp[0][0] = 1;
156
-
157
- for(int i = 0; i < N - 1; ++i){
158
-
159
- for(int j = 0; j <= (K + sumC) / 2; ++j){
160
-
161
- if(C[i] <= j){
162
-
163
- dp[i + 1][j] += dp[i][j - C[i]];
164
-
165
- dp[i + 1][j] %= mod;
166
-
167
- }
168
-
169
- dp[i + 1][j] += dp[i][j];
170
-
171
- dp[i + 1][j] %= mod;
172
-
173
- }
174
-
175
- }
176
-
177
-
178
-
179
- cout << dp[N - 1][(K + sumC) / 2] << endl;
180
-
181
- }
182
-
183
-
184
-
185
- ```
186
-
187
179
 
188
180
 
189
181
  ### 試したこと
@@ -221,5 +213,3 @@
221
213
  ### 補足情報（FW/ツールのバージョンなど）
222
214
 
223
215
  使用しているコンパイラ...gcc12.0.5
224
-
225
- ここにより詳細な情報を記載してください。