QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #118337 | #2596. Even Forest | solemntee# | WA | 689ms | 210324kb | C++20 | 2.1kb | 2023-07-03 13:26:18 | 2023-07-03 13:26:19 |
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]=dp[x][0][1]=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][0][1]=min(dp[to][0][0]+1,dp[x][1][1]+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]+min(dp[to][1][1],dp[to][0][0])+1);
tdp[0][1]=dp[x][0][1]+min(dp[to][0][0],dp[to][1][1])+1;
tdp[1][0]=min(dp[x][1][0]+min(dp[to][0][0],dp[to][1][1])+1,dp[x][0][1]+dp[to][0][0]);
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][0][0],dp[to][1][1])+1});
dp[x][0][0]=tdp[0][0];
dp[x][0][1]=tdp[0][1];
dp[x][1][0]=tdp[1][0];
dp[x][1][1]=tdp[1][1];
}
}
if(son==0){
dp[x][0][0]=0;
dp[x][0][1]=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({n-1,dp[1][0][0],dp[1][1][1],dp[1][0][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: 3696kb
input:
4 1 2 2 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3676kb
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: 3632kb
input:
1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
2 1 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
3 2 3 3 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
4 2 3 3 1 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
5 4 2 2 3 4 1 5 3
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
6 4 3 1 4 2 4 5 2 4 6
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3656kb
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:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 689ms
memory: 210324kb
input:
1000000 851841 325834 455962 325834 135775 325834 525341 325834 265267 325834 868520 325834 834325 325834 867971 325834 325834 879726 325834 242607 325834 106951 122113 325834 325834 499633 727580 325834 325834 200171 325834 178877 325834 493841 957118 325834 325834 809324 325834 641895 325834 33338...
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
3 2 1 2 3
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
4 4 3 1 4 1 2
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
5 1 4 2 4 3 2 3 5
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
6 3 5 3 6 1 6 1 4 4 2
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
7 1 2 3 2 6 3 6 7 7 4 4 5
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
8 6 2 1 2 8 1 5 8 5 7 7 3 4 3
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
20 6 1 6 15 9 15 18 9 18 17 17 7 8 7 3 8 19 3 2 19 13 2 13 11 12 11 12 14 4 14 4 5 20 5 16 20 16 10
output:
1
result:
ok 1 number(s): "1"
Test #19:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
42 33 30 17 33 17 7 29 7 15 29 15 23 23 1 10 1 10 31 4 31 12 4 12 34 28 34 28 41 41 11 32 11 32 24 13 24 13 19 26 19 16 26 35 16 35 27 37 27 37 3 3 20 8 20 39 8 6 39 6 42 14 42 14 38 38 9 25 9 18 25 18 5 36 5 36 40 40 21 21 2 22 2
output:
1
result:
ok 1 number(s): "1"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
27 19 14 6 19 16 19 19 7 19 4 21 19 26 4 26 15 4 5 5 1 10 26 13 26 17 7 3 4 23 13 21 25 2 25 2 12 10 9 20 17 24 16 21 27 22 13 8 16 18 7 11 24
output:
6
result:
ok 1 number(s): "6"
Test #21:
score: -100
Wrong Answer
time: 0ms
memory: 4128kb
input:
2007 1852 380 380 1300 1437 380 380 1789 380 876 380 1427 1295 1852 380 1549 782 1549 205 380 1789 446 1300 1113 380 417 446 1357 1295 242 446 1758 579 417 562 242 1086 1437 1584 876 579 1981 1873 1789 1918 1789 376 1437 1113 1564 30 1113 1357 1197 221 446 1300 128 386 579 1918 1126 479 1549 1026 15...
output:
338
result:
wrong answer 1st numbers differ - expected: '326', found: '338'