QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #118323 | #2596. Even Forest | solemntee# | WA | 693ms | 210272kb | C++20 | 2.1kb | 2023-07-03 13:05:29 | 2023-07-03 13:05:33 |
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;
dp[x][0][1]=0;//表示全断开
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]+dp[to][0][0]+1);
tdp[0][1]=dp[x][0][1]+min(dp[to][0][0]+1,dp[x][1][1]+1);
tdp[1][0]=min(dp[x][1][0]+min(dp[to][1][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][1][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({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: 1ms
memory: 3640kb
input:
4 1 2 2 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
4 1 2 1 3 1 4
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3640kb
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: 3640kb
input:
1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
2 1 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
3 2 3 3 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
4 2 3 3 1 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3684kb
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: 3724kb
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: 3688kb
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: 693ms
memory: 210272kb
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: 1ms
memory: 3636kb
input:
3 2 1 2 3
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
4 4 3 1 4 1 2
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3632kb
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: 3628kb
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: 3632kb
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: 3632kb
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: 3668kb
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: 3680kb
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: 3672kb
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: 2ms
memory: 4044kb
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:
330
result:
wrong answer 1st numbers differ - expected: '326', found: '330'