oj.uz

답안 #697218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697218 2023-02-08T23:33:15 Z allllekssssa Bomb (IZhO17_bomb) C++14
0 / 100
 73 ms 131072 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define pii pair<int, int>

const int maxN = 1e6 + 10;

pii d[maxN];
long long ans;
long long ways = 1;
int n;
vector<int> v[maxN];


void dfs1(int x, int pred) {
    
    d[x] = {0, 1};
	for (int i: v[x]) {
		if (i != pred) {
			dfs1(i, x);
			if (d[i].first + 1 > d[x].first) {
				d[x] = {d[i].first + 1, d[i].second};
			} else {
				if (d[i].first + 1 == d[x].first) {
					d[x].second+=d[i].second;
				}
			}
		} 
	}
}

void dfs2(int x, int pred, pii bestUp) {
     
	vector<pii> choices;
    
    choices.pb(bestUp);

	for (int i: v[x]) {
		if (i != pred) {
			choices.pb(d[i]);
		}
	}

	sort(choices.begin(), choices.end());
	reverse(choices.begin(), choices.end());
    
    if (choices.size() > 2) {

    	long long maxProduct = 1ll * (choices[0].first + 1) * (choices[1].first + choices[2].first + 2);

    	if (maxProduct  >= ans) {
    		if (maxProduct == 4) cout << x << endl;
    		long long pathCount = 0;

    		if (choices[1].first == choices[2].first) {
                
    			long long total = 0;
                long long removeSum = 0;
    			for (auto i: choices) {
    				if (choices[1].first == i.first) {
    					total+=i.second;
    					removeSum+= 1ll * i.second * i.second; 
    				}
    			}
                
    			pathCount = total * total - removeSum;
    			pathCount/=2;

    		} else {
    				if (choices[0].first == choices[1].first) {
                        
    				    long long total = 0;
    		        	for (auto i: choices) {
    				    	if (choices[2].first == i.first) {
    						  	total+=i.second;
  		  					}
    					}

    					pathCount =  total * (choices[0].second + choices[1].second);

    				} else {
    					 
    					 long long total = 0;
    		        	 for (auto i: choices) {
    				    	if (choices[2].first == i.first) {
    						  	total+=i.second;
  		  					}
    					}

    					pathCount = total * choices[1].second;
    				}
    		}

    		if (maxProduct == ans) ways+=pathCount; else {
    			ans = maxProduct;
    			ways = pathCount;
    		}
    	}
    }
    
    // leaf
    if (v[x].size() == 1 && pred) {
    	return;
    }
   

    int len = choices[0].first;
    int nacini = 0;
    int drugiNacini = 0;

    for (auto i: choices) {
    	if (i.first == len) nacini+=i.second;
    	if (i.first == choices[1].first) drugiNacini+=i.second;
    }

	for (int i: v[x]) {
		if (i != pred) {
			if (d[i].first == len) {
				if (nacini - d[i].second != 0) {
				   dfs2(i, x, {len + 1, nacini - d[i].second});
				} else {
					dfs2(i, x, {choices[1].first + 1, drugiNacini});
				}
			} else {
				dfs2(i, x, {len + 1, nacini});
			}
		}
	}
}

int main() {
    
    cin >> n;
   
    for (int i = 1; i<n; i++) {
    	int x, y;
    	scanf("%d%d", &x, &y);
    	v[x].pb(y);
    	v[y].pb(x);
    }


    dfs1(1, 0);

    dfs2(1, 0, {-1, 1});
  
    cout << ans << " " << ways << endl;
	return 0;
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:139:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |      scanf("%d%d", &x, &y);
      |      ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 23792 KB Output isn't correct
2 Runtime error 67 ms 131072 KB Execution killed with signal 9
3 Incorrect 73 ms 23928 KB Output isn't correct
4 Incorrect 69 ms 23924 KB Output isn't correct
5 Incorrect 12 ms 23764 KB Output isn't correct
6 Incorrect 12 ms 23764 KB Output isn't correct
7 Incorrect 12 ms 23792 KB Output isn't correct
8 Runtime error 31 ms 47944 KB Execution killed with signal 11
9 Runtime error 29 ms 47960 KB Execution killed with signal 11
10 Runtime error 30 ms 47972 KB Execution killed with signal 11
11 Runtime error 33 ms 47924 KB Execution killed with signal 11
12 Runtime error 39 ms 47948 KB Execution killed with signal 11
13 Runtime error 35 ms 47960 KB Execution killed with signal 11
14 Runtime error 33 ms 47908 KB Execution killed with signal 11
15 Runtime error 34 ms 47948 KB Execution killed with signal 11
16 Runtime error 31 ms 47964 KB Execution killed with signal 11
17 Incorrect 13 ms 23792 KB Output isn't correct
18 Incorrect 15 ms 23800 KB Output isn't correct
19 Incorrect 13 ms 23752 KB Output isn't correct
20 Incorrect 13 ms 23800 KB Output isn't correct
21 Incorrect 13 ms 23764 KB Output isn't correct
22 Incorrect 12 ms 23764 KB Output isn't correct
23 Incorrect 14 ms 23800 KB Output isn't correct
24 Incorrect 14 ms 23792 KB Output isn't correct
25 Incorrect 16 ms 23868 KB Output isn't correct
26 Incorrect 13 ms 23764 KB Output isn't correct
27 Incorrect 14 ms 23796 KB Output isn't correct
28 Incorrect 14 ms 23804 KB Output isn't correct
29 Incorrect 16 ms 23796 KB Output isn't correct
30 Incorrect 16 ms 24000 KB Output isn't correct
31 Incorrect 15 ms 23892 KB Output isn't correct
32 Incorrect 16 ms 23868 KB Output isn't correct
33 Incorrect 15 ms 23956 KB Output isn't correct
34 Incorrect 16 ms 23856 KB Output isn't correct
35 Incorrect 18 ms 23988 KB Output isn't correct
36 Incorrect 16 ms 23928 KB Output isn't correct
37 Runtime error 34 ms 47964 KB Execution killed with signal 11
38 Incorrect 48 ms 24932 KB Output isn't correct
39 Runtime error 38 ms 47936 KB Execution killed with signal 11
40 Incorrect 20 ms 24320 KB Output isn't correct
41 Runtime error 32 ms 48020 KB Execution killed with signal 11
42 Incorrect 13 ms 23716 KB Output isn't correct
43 Incorrect 48 ms 24884 KB Output isn't correct
44 Incorrect 18 ms 23892 KB Output isn't correct
45 Incorrect 52 ms 24936 KB Output isn't correct
46 Incorrect 51 ms 24900 KB Output isn't correct
47 Incorrect 46 ms 24940 KB Output isn't correct
48 Incorrect 49 ms 24896 KB Output isn't correct
49 Incorrect 48 ms 24900 KB Output isn't correct
50 Incorrect 57 ms 24864 KB Output isn't correct
51 Incorrect 46 ms 24908 KB Output isn't correct
52 Incorrect 47 ms 24908 KB Output isn't correct
53 Incorrect 47 ms 24904 KB Output isn't correct
54 Incorrect 49 ms 24904 KB Output isn't correct
55 Incorrect 49 ms 24868 KB Output isn't correct
56 Incorrect 47 ms 24936 KB Output isn't correct
57 Incorrect 49 ms 24840 KB Output isn't correct
58 Incorrect 49 ms 24968 KB Output isn't correct
59 Incorrect 50 ms 25072 KB Output isn't correct
60 Incorrect 47 ms 24856 KB Output isn't correct
61 Incorrect 49 ms 24916 KB Output isn't correct
62 Incorrect 47 ms 24900 KB Output isn't correct
63 Incorrect 48 ms 24876 KB Output isn't correct
64 Incorrect 44 ms 24948 KB Output isn't correct
65 Incorrect 46 ms 24976 KB Output isn't correct
66 Incorrect 46 ms 24924 KB Output isn't correct
67 Incorrect 46 ms 24904 KB Output isn't correct
68 Incorrect 45 ms 25076 KB Output isn't correct
69 Incorrect 45 ms 24908 KB Output isn't correct
70 Incorrect 36 ms 24388 KB Output isn't correct
71 Incorrect 46 ms 24864 KB Output isn't correct
72 Incorrect 46 ms 24884 KB Output isn't correct
73 Incorrect 44 ms 24944 KB Output isn't correct
74 Incorrect 45 ms 24908 KB Output isn't correct
75 Incorrect 47 ms 24868 KB Output isn't correct
76 Incorrect 46 ms 24936 KB Output isn't correct
77 Incorrect 45 ms 24948 KB Output isn't correct
78 Incorrect 45 ms 24964 KB Output isn't correct
79 Incorrect 45 ms 24952 KB Output isn't correct
80 Incorrect 45 ms 24808 KB Output isn't correct
81 Incorrect 46 ms 24832 KB Output isn't correct
82 Incorrect 44 ms 24820 KB Output isn't correct
83 Incorrect 46 ms 24820 KB Output isn't correct
84 Incorrect 49 ms 24860 KB Output isn't correct
85 Incorrect 48 ms 24808 KB Output isn't correct
86 Incorrect 44 ms 24780 KB Output isn't correct
87 Incorrect 47 ms 24824 KB Output isn't correct
88 Incorrect 43 ms 24832 KB Output isn't correct
89 Incorrect 46 ms 24824 KB Output isn't correct
90 Incorrect 33 ms 24780 KB Output isn't correct
91 Incorrect 45 ms 24676 KB Output isn't correct
92 Incorrect 46 ms 24648 KB Output isn't correct
93 Incorrect 44 ms 24524 KB Output isn't correct
94 Incorrect 47 ms 24532 KB Output isn't correct
95 Incorrect 51 ms 24548 KB Output isn't correct
96 Incorrect 46 ms 24564 KB Output isn't correct
97 Incorrect 47 ms 24508 KB Output isn't correct
98 Incorrect 46 ms 24556 KB Output isn't correct
99 Incorrect 47 ms 24512 KB Output isn't correct
100 Incorrect 44 ms 24568 KB Output isn't correct