QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#605456#2514. Cable Protectionucup-team3474AC ✓50ms30016kbC++201.1kb2024-10-02 17:19:332024-10-02 17:19:34

Judging History

This is the latest submission verdict.

  • [2024-10-02 17:19:34]
  • Judged
  • Verdict: AC
  • Time: 50ms
  • Memory: 30016kb
Show
  • [2024-10-02 17:19:33]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1919810,mod=1e9+7;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];

vector<int> e[N];
ll dp1[N][2],dp2[N][2];
int root1,root2;

void dfs1(int x,int fa){
    // cout<<x<<" "<<fa<<endl;
    dp1[x][1]=1;
    for(auto j:e[x]){
        if(j==fa||j==root1) continue;
        dfs1(j,x);
        dp1[x][0]+=dp1[j][1];
        dp1[x][1]+=min(dp1[j][0],dp1[j][1]);
    }
}

void dfs2(int x,int fa){
    // cout<<x<<" "<<fa<<endl;
    dp2[x][1]=1;
    for(auto j:e[x]){
        if(j==fa||j==root2) continue;
        dfs2(j,x);
        dp2[x][0]+=dp2[j][1];
        dp2[x][1]+=min(dp2[j][0],dp2[j][1]);
    }
}


int main(){
    cin>>n>>m;
    for(int i=1;i<=n+m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
        if(u==0&&v<n) root2=v;
        else if(v==0&&u<n) root2=u;
    }
    // cout<<root1<<" "<<root2<<endl;
    dfs1(root1,root2);
    dfs2(root2,root1);
    cout<<min(min(dp1[root1][0]+1,dp1[root1][1]),min(dp2[root2][0]+1,dp2[root2][1]))<<endl;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 5676kb

input:

3 2
0 1
1 2
0 2
1 3
2 4

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 2ms
memory: 5664kb

input:

5 5
0 1
1 2
2 3
3 4
0 4
0 5
1 6
2 7
3 8
4 9

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 2ms
memory: 6004kb

input:

700 300
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
51 52...

output:

446

result:

ok single line: '446'

Test #4:

score: 0
Accepted
time: 4ms
memory: 6784kb

input:

4000 6000
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
51 ...

output:

4129

result:

ok single line: '4129'

Test #5:

score: 0
Accepted
time: 25ms
memory: 15580kb

input:

100 99900
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
51 ...

output:

40317

result:

ok single line: '40317'

Test #6:

score: 0
Accepted
time: 2ms
memory: 5764kb

input:

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

output:

7

result:

ok single line: '7'

Test #7:

score: 0
Accepted
time: 2ms
memory: 5680kb

input:

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

output:

5

result:

ok single line: '5'

Test #8:

score: 0
Accepted
time: 2ms
memory: 5828kb

input:

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

output:

7

result:

ok single line: '7'

Test #9:

score: 0
Accepted
time: 2ms
memory: 5872kb

input:

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

output:

5

result:

ok single line: '5'

Test #10:

score: 0
Accepted
time: 50ms
memory: 30016kb

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:

84571

result:

ok single line: '84571'

Test #11:

score: 0
Accepted
time: 2ms
memory: 5864kb

input:

125 375
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
51 52...

output:

205

result:

ok single line: '205'

Test #12:

score: 0
Accepted
time: 2ms
memory: 5832kb

input:

3 2
0 1
1 2
0 2
1 3
2 4

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 0ms
memory: 5732kb

input:

4 1
0 1
1 2
2 3
0 3
1 4

output:

2

result:

ok single line: '2'

Test #14:

score: 0
Accepted
time: 14ms
memory: 14388kb

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:

25437

result:

ok single line: '25437'

Test #15:

score: 0
Accepted
time: 2ms
memory: 5748kb

input:

6 1
0 1
1 2
2 3
3 4
4 5
0 5
0 6

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 0ms
memory: 5684kb

input:

7 1
0 1
1 2
2 3
3 4
4 5
5 6
0 6
0 7

output:

4

result:

ok single line: '4'
English 繁體中文 简体中文

伺服器時間: 2025-02-08 15:51:23 | 開源專案