QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#118341	#2596. Even Forest	solemntee^#	WA	647ms	210124kb	C++20	2.1kb	2023-07-03 13:31:16	2023-07-03 13:31:20

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-07-03 13:31:20]
评测

测评结果：WA
用时：647ms
内存：210124kb

查看

[2023-07-03 13:31:16]
提交

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]=1e9;

                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
*/

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok 1 number(s): "1"

Test #2:

score: 0

Accepted

time: 1ms

memory: 3628kb

input:

output:

result:

ok 1 number(s): "0"

Test #3:

score: 0

Accepted

time: 1ms

memory: 3632kb

input:

output:

result:

ok 1 number(s): "1"

Test #4:

score: 0

Accepted

time: 1ms

memory: 3632kb

input:

output:

result:

ok 1 number(s): "0"

Test #5:

score: 0

Accepted

time: 1ms

memory: 3724kb

input:

2
1 2

output:

result:

ok 1 number(s): "1"

Test #6:

score: 0

Accepted

time: 1ms

memory: 3680kb

input:

3
2 3
3 1

output:

result:

ok 1 number(s): "0"

Test #7:

score: 0

Accepted

time: 1ms

memory: 3644kb

input:

output:

result:

ok 1 number(s): "0"

Test #8:

score: 0

Accepted

time: 0ms

memory: 3676kb

input:

output:

result:

ok 1 number(s): "0"

Test #9:

score: 0

Accepted

time: 1ms

memory: 3624kb

input:

output:

result:

ok 1 number(s): "1"

Test #10:

score: 0

Accepted

time: 1ms

memory: 3684kb

input:

output:

result:

ok 1 number(s): "0"

Test #11:

score: -100

Wrong Answer

time: 647ms

memory: 210124kb

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'