Submission #697212

#	Time	Username	Problem	Language	Result	Execution time	Memory
697212		allllekssssa	Hard route (IZhO17_road)	C++14	0 / 100	13 ms	23768 KiB

road

#include<bits/stdc++.h>

using namespace std;

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

const int maxN = 1e6 + 10;

pii d[maxN];
int 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) {
    		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 (stderr)

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

• Subtask 1: 0 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48