QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #118316 | #2596. Even Forest | solemntee# | WA | 1ms | 3680kb | C++20 | 1.8kb | 2023-07-03 12:56:10 | 2023-07-03 12:56:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
vector<vector<int>>v(n+1,vector<int>());
for(int i=1;i<n;i++){
int tu,tv;
scanf("%d%d",&tu,&tv);
v[tu].push_back(tv);
v[tv].push_back(tu);
}
vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(2,vector<int>(2)));
function<void(int,int)>dfs=[&](int x,int pre){
int son=0;
dp[x][1][0]=dp[x][1][1]=dp[x][0][0]=1e9;
for(auto to:v[x])if(to!=pre){
son++;
dfs(to,x);
if(son==1){
dp[x][0][0]=min({dp[to][1][0],dp[to][1][1],dp[to][0][0]+1});
dp[x][1][0]=dp[to][0][0];
}else{
vector<vector<int>>tdp(2,vector<int>(2));
tdp[0][0]=tdp[0][1]=tdp[1][0]=tdp[1][1]=1e9;
tdp[0][0]=min(dp[x][0][0]+min(dp[to][1][1],dp[to][1][0]),dp[x][0][0]+dp[to][0][0]+1);
tdp[1][0]=dp[x][1][0]+min(dp[to][1][0],dp[to][1][1])+1;
tdp[1][1]=min({dp[x][1][0]+dp[to][0][0],dp[x][1][1]+dp[to][0][0],dp[x][1][1]+min(dp[to][1][0],dp[to][1][1])+1});
dp[x][0][0]=tdp[0][0];
dp[x][1][0]=tdp[1][0];
dp[x][1][1]=tdp[1][1];
}
}
if(son==0){
dp[x][0][0]=0;
dp[x][1][0]=dp[x][1][1]=1e9;
}
// for(int i=0;i<=1;i++){
// for(int j=0;j<=1;j++){
// printf("dp[%d][%d][%d]=%d\n",x,i,j,dp[x][i][j]);
// }
// }
};
dfs(1,1);
int ans=min(dp[1][0][0],dp[1][1][1]);
printf("%d",ans);
return 0;
}
/*
4
1 2
2 3
3 4
4
1 2
1 3
1 4
5
1 2
1 3
1 4
4 5
8
1 2
2 3
2 4
1 5
5 6
6 7
6 8
7
1 2
1 3
3 4
1 5
1 6
6 7
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
4 1 2 2 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
4 1 2 1 3 1 4
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
6 1 2 2 3 4 2 4 5 6 4
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
2 1 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
3 2 3 3 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
4 2 3 3 1 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
5 4 2 2 3 4 1 5 3
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
6 4 3 1 4 2 4 5 2 4 6
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3608kb
input:
50 21 22 22 27 22 7 22 12 22 13 43 22 36 22 35 22 6 22 10 22 22 38 19 22 34 22 8 22 22 44 22 3 9 22 22 16 23 22 18 22 22 25 22 5 22 2 22 15 46 22 37 22 48 22 33 22 22 17 31 22 22 29 22 28 22 49 4 22 22 26 41 22 22 32 22 50 22 20 22 30 24 22 40 22 22 45 14 22 22 11 42 22 39 22 1 22 47 22
output:
-2064771044
result:
wrong answer 1st numbers differ - expected: '0', found: '-2064771044'