QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #118342 | #2596. Even Forest | solemntee# | WA | 675ms | 210196kb | C++20 | 2.1kb | 2023-07-03 13:31:36 | 2023-07-03 13:31:39 |
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]=1e6;//表示全断开
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],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]=1e6;
tdp[0][0]=min(dp[x][0][0]+min(dp[to][1][1],dp[to][1][0]),dp[x][0][0]+dp[to][1][1]+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]=1e6;
}
// 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: 1ms
memory: 3596kb
input:
4 1 2 2 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
4 1 2 1 3 1 4
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3632kb
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: 0ms
memory: 3720kb
input:
1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
2 1 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
3 2 3 3 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
4 2 3 3 1 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3680kb
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: 3560kb
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: 3648kb
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: -100
Wrong Answer
time: 675ms
memory: 210196kb
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:
-730379966
result:
wrong answer 1st numbers differ - expected: '0', found: '-730379966'