ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 25.07.2019 17:20:39

ამოცანა: ხე

მომხმარებელი: lukamosiashvili

ვერდიქტი: ნაწილობრივი ამოხსნა

შეფასება: 70.0 ქულა







#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,dp[109],dpsh[109],msh[109],kari,pas,z[4],zi;
vector <int> v[109],g[109];
void up(int q){
	if(msh[q]==kari){
		zi++;
		z[zi]=q;
		return;
	}
	pas+=dpsh[msh[q]]-dp[q];
	up(msh[q]);
}
void dfs(int q, int w){
	msh[q]=w;
	g[q].push_back(q);
	dp[q]=205;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q);
		dpsh[q]+=dp[(*it)];
		for(int h=0; h<g[(*it)].size(); h++){
			g[q].push_back(g[(*it)][h]);
		}
	}
	for(int ii=0; ii<g[q].size(); ii++){
		if(g[q][ii]==q) continue;
		int i=g[q][ii];
		pas=0;
		zi=0;
		kari=q;
		up(i);
		pas+=dpsh[q]-dp[z[1]]+1+dpsh[i];
		if(dp[q]>pas) dp[q]=pas;
		for(int jj=0; jj<g[q].size(); jj++){
			if(g[q][jj]==i||g[q][jj]==q) continue;
			int j=g[q][jj];
			pas=dpsh[i]+dpsh[j]+1;
			kari=q;
			zi=0;
			up(i);
			up(j);
			if(zi!=2) continue;
			pas+=dpsh[q]-dp[z[1]]-dp[z[2]];
			if(dp[q]>pas) dp[q]=pas;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(b=1; b<a; b++){
		cin>>c>>d;
		v[c].push_back(d);
		v[d].push_back(c);
	}
	dfs(1,0);
	if(dp[1]==205) cout<<-1; else cout<<dp[1];
	return 0;
}

ტესტები

შემავალი მონაცემები
18
1 16
16 17
17 18
1 2
1 3
1 4
3 5
3 7
4 8
13 14
9 13
4 9
5 10
10 15
3 6
6 11
7 12
გამომავალი მონაცემები
4
თქვენი პასუხი
4
ჩეკერის პასუხი
YES
შემავალი მონაცემები
49
49 33
18 19
43 47
47 1
1 39
9 10
3 9
2 3
38 2
38 4
38 5
5 6
6 7
7 8
6 48
37 48
37 35
34 35
36 37
36 33
37 1
1 40
40 31
31 32
32 30
29 30
28 29
26 28
27 28
19 30
19 20
20 21
21 25
21 22
24 25
25 23
17 18
18 15
14 15
13 15
15 16
11 12
12 13
41 47
42 47
42 44
44 45
45 46
გამომავალი მონაცემები
12
თქვენი პასუხი
12
ჩეკერის პასუხი
YES
შემავალი მონაცემები
75
13 73
73 74
14 71
71 72
54 70
3 1
3 4
3 5
4 31
4 32
32 34
32 33
33 39
37 38
33 35
33 36
36 37
5 67
5 6
5 7
5 8
8 9
8 10
8 11
11 12
11 13
11 14
11 15
11 16
11 17
16 19
23 24
20 23
19 20
17 18
18 21
21 22
25 27
26 27
27 68
2 67
30 67
29 67
29 68
28 40
28 68
40 69
41 69
42 69
42 70
70 53
70 52
70 43
51 52
51 50
50 47
50 49
48 49
45 46
44 45
44 43
65 66
65 64
64 58
56 58
54 56
54 55
55 57
57 59
59 60
60 61
61 62
62 63
3 75
გამომავალი მონაცემები
19
თქვენი პასუხი
17
ჩეკერის პასუხი
NO
შემავალი მონაცემები
100
4 2
4 55
43 55
42 55
55 41
55 40
55 39
4 20
1 20
4 57
57 58
57 56
56 59
57 83
59 60
60 61
61 62
62 63
63 64
64 65
65 66
67 66
68 69
70 71
71 68
73 74
72 73
72 71
76 77
77 75
77 78
78 79
79 80
80 53
53 54
54 44
44 45
44 42
41 46
46 47
40 48
48 49
49 50
50 51
50 52
83 84
83 85
93 83
93 91
93 92
88 85
88 89
89 90
85 87
85 86
66 68
53 81
81 82
81 94
94 95
95 96
96 97
96 98
99 98
99 100
38 39
32 39
30 39
28 39
27 39
10 39
34 32
33 32
33 35
33 36
22 36
21 36
21 19
19 18
17 18
18 16
30 31
31 37
23 37
28 29
29 24
26 27
26 25
10 11
11 12
12 13
13 14
14 15
9 10
8 9
7 8
6 7
5 6
3 5
გამომავალი მონაცემები
23
თქვენი პასუხი
22
ჩეკერის პასუხი
NO
შემავალი მონაცემები
42
1 33
2 33
8 33
8 32
8 9
8 11
11 10
11 12
12 35
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
12 13
12 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
22 21
21 23
24 3
4 24
24 25
25 26
26 27
5 27
6 28
27 28
28 29
7 29
29 30
30 31
31 32
გამომავალი მონაცემები
9
თქვენი პასუხი
9
ჩეკერის პასუხი
YES
შემავალი მონაცემები
33
6 2
2 3
3 4
4 5
5 1
1 7
7 8
8 9
9 10
10 11
11 12
12 18
18 19
20 21
22 21
17 22
10 17
13 14
14 15
15 16
16 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
30 33
33 32
6 33
გამომავალი მონაცემები
3
თქვენი პასუხი
3
ჩეკერის პასუხი
YES
შემავალი მონაცემები
35
6 21
1 22
2 23
6 23
6 24
6 22
6 18
17 18
16 17
15 16
11 15
20 21
19 20
14 19
10 11
9 10
8 9
4 8
3 12
12 13
13 14
8 7
5 7
24 25
25 26
33 35
33 31
31 32
33 34
25 27
27 29
27 28
30 29
29 31
გამომავალი მონაცემები
-1
თქვენი პასუხი
7
ჩეკერის პასუხი
NO
შემავალი მონაცემები
40
6 21
1 22
2 23
6 23
6 24
6 22
6 18
17 18
16 17
15 16
11 15
20 21
19 20
14 19
10 11
9 10
8 9
4 8
3 12
12 13
13 14
8 7
5 7
24 25
25 26
33 35
33 31
31 32
33 34
25 27
27 29
27 28
30 29
29 31
1 36
36 37
37 38
39 38
39 40
გამომავალი მონაცემები
8
თქვენი პასუხი
8
ჩეკერის პასუხი
YES
შემავალი მონაცემები
18
1 2
2 3
3 4
3 5
2 6
6 7
7 12
1 8
8 15
8 9
9 10
10 11
1 13
13 14
14 16
15 17
15 18
გამომავალი მონაცემები
4
თქვენი პასუხი
4
ჩეკერის პასუხი
YES
შემავალი მონაცემები
21
1 2
2 3
2 4
4 5
4 6
6 7
7 8
6 9
9 10
10 11
10 12
12 17
17 18
18 19
6 13
13 14
14 15
15 16
1 20
20 21
გამომავალი მონაცემები
5
თქვენი პასუხი
5
ჩეკერის პასუხი
YES