oj.uz

Submission #697221

# Submission time Handle Problem Language Result Execution time Memory
697221 2023-02-08T23:40:28 Z allllekssssa Hard route (IZhO17_road) C++14
0 / 100
 13 ms 23796 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;
    
    if (x != 1) {
      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) {
    		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 = 1;
    int drugiDuzina = -1;
    if (choices.size() > 1) {
    	drugiDuzina = choices[1].first;
    	drugiDuzina = 0;
    }

    for (auto i: choices) {
    	if (i.first == len) nacini+=i.second;
    	if (choices.size() > 1 && drugiDuzina == 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, {drugiDuzina + 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, {0, 0});
  
    cout << ans << " " << ways << endl;
	return 0;
}

Compilation message

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

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23756 KB Output is correct
3 Correct 11 ms 23756 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23792 KB Output is correct
6 Correct 12 ms 23796 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 12 ms 23796 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23756 KB Output is correct
3 Correct 11 ms 23756 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23792 KB Output is correct
6 Correct 12 ms 23796 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 12 ms 23796 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23756 KB Output is correct
3 Correct 11 ms 23756 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23792 KB Output is correct
6 Correct 12 ms 23796 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 12 ms 23796 KB Output isn't correct
9 Halted 0 ms 0 KB -