QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#762282	#2514. Cable Protection	SanguineChameleon^#	AC ✓	30ms	17904kb	C++20	1.6kb	2024-11-19 14:25:34	2024-11-19 14:25:42

Judging History

This is the latest submission verdict.

[2024-11-19 14:25:42]
Judged

Verdict: AC
Time: 30ms
Memory: 17904kb

Show

[2024-11-19 14:25:34]
Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define mp make_pair
#define eb emplace_back
#define pb push_back
typedef pair<int,int> pii;

const int mxn=3e5+5;

vector<int> adjl[mxn];
int dp[mxn][2];
void dfs(int nd, int p=-1){
    dp[nd][1]=1;//mark cur node
    dp[nd][0]=0;
    for(int x:adjl[nd]){
        if(x==p)continue;
        dfs(x,nd);
        dp[nd][1]+=dp[x][0];
        dp[nd][0]+=dp[x][1];
    }
    dp[nd][0] = min(dp[nd][0], dp[nd][1]);
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n+m;i++){
        int a,b;
        cin>>a>>b;
        if(max(a,b)<n){//part of main cycle 0...n-1
            continue;
        }
        adjl[a].pb(b);
        adjl[b].pb(a);
    }
    for(int i=0;i<n;i++){
        dfs(i);//find the dp
    }
    int mdp[n][2];
    mdp[0][0]=dp[0][0];
    mdp[0][1]=dp[0][1];
    for(int i=1;i<n;i++){
        mdp[i][1] = mdp[i-1][0] + dp[i][1];
        mdp[i][0] = mdp[i-1][1] + dp[i][0];

        mdp[i][0] = min(mdp[i][0],mdp[i][1]);
    }
    int ans=mdp[n-1][1];//case 1: force take n-1

    mdp[0][0]=dp[0][1];
    for(int i=1;i<n;i++){
        mdp[i][1] = mdp[i-1][0] + dp[i][1];
        mdp[i][0] = mdp[i-1][1] + dp[i][0];

        mdp[i][0] = min(mdp[i][0],mdp[i][1]);
    }
    ans = min(ans, mdp[n-1][0]);//case 2: force take 0
    cout<<ans;
}
/*
3 2
0 1
1 2
0 2
1 3
2 4

4 11
0 1
0 3
0 4
0 5
1 2
1 6
2 3
2 9
3 12
6 7
6 8
9 10
10 11
12 13
12 14

*/

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3684kb

input:

output:

result:

ok single line: '2'

Test #2:

score: 0

Accepted

time: 1ms

memory: 3720kb

input:

output:

result:

ok single line: '5'

Test #3:

score: 0

Accepted

time: 1ms

memory: 3792kb

input:

output:

result:

ok single line: '446'

Test #4:

score: 0

Accepted

time: 2ms

memory: 4408kb

input:

output:

result:

ok single line: '4129'

Test #5:

score: 0

Accepted

time: 20ms

memory: 11928kb

input:

output:

result:

ok single line: '40317'

Test #6:

score: 0

Accepted

time: 1ms

memory: 3684kb

input:

output:

result:

ok single line: '7'

Test #7:

score: 0

Accepted

time: 1ms

memory: 3740kb

input:

output:

result:

ok single line: '5'

Test #8:

score: 0

Accepted

time: 1ms

memory: 3680kb

input:

output:

result:

ok single line: '7'

Test #9:

score: 0

Accepted

time: 1ms

memory: 3680kb

input:

output:

result:

ok single line: '5'

Test #10:

score: 0

Accepted

time: 30ms

memory: 17904kb

input:

100000 100000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

result:

ok single line: '84571'

Test #11:

score: 0

Accepted

time: 1ms

memory: 3756kb

input:

output:

result:

ok single line: '205'

Test #12:

score: 0

Accepted

time: 1ms

memory: 3608kb

input:

output:

result:

ok single line: '2'

Test #13:

score: 0

Accepted

time: 1ms

memory: 3668kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 3ms

memory: 9372kb

input:

30001 30000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
5...

output:

result:

ok single line: '25437'

Test #15:

score: 0

Accepted

time: 1ms

memory: 3720kb

input:

output:

result:

ok single line: '3'

Test #16:

score: 0

Accepted

time: 1ms

memory: 3720kb

input:

output:

result:

ok single line: '4'