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

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


გაგზავნის თარიღი: 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...
გამომავალი მონაცემები
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...
გამომავალი მონაცემები
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...
გამომავალი მონაცემები
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...
გამომავალი მონაცემები
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 4...
გამომავალი მონაცემები
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