Submission #93015

#	Time	Username	Problem	Language	Result	Execution time	Memory
93015		davitmarg	Hard route (IZhO17_road)	C++17	19 / 100	2062 ms	131192 KiB

road

/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <cassert>
#include <fstream>  
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;

const int N = 5003;

int n,used[N][N],st;
vector<int> g[N],ord;
pair<LL, LL> dp[N][N];
LL  best;
map<LL, int> u;
void dfsinit(int v)
{
	used[st][v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (used[st][to] == 1)
			continue;
		dfsinit(to);
		if (dp[st][to].first + 1 >= dp[st][v].first)
		{
			dp[st][v].second = dp[st][v].first;
			dp[st][v].first = dp[st][to].first + 1;
		}
		else if (dp[st][to].first + 1 >= dp[st][v].second)
			dp[st][v].second = dp[st][to].first + 1;
	}
}

void dfs(int v, LL d = 0, LL h = 0)
{
	used[st][v] = 2;
	if (g[v].size() == 1 && st!=v)
	{
		best = max(best, h*d);
		u[h*d]++;
	}
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (used[st][to]==2)
			continue;
		LL H;
		if (dp[st][to].first + 1 == dp[st][v].first)
			H = max(h,dp[st][v].second);
		else
			H = max(h, dp[st][v].first);
		dfs(to,d+1,H);
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n-1; i++)
	{
		int a, b;
		cin >> a >> b;
		g[a].PB(b);
		g[b].PB(a);
	}
	for (st = 1; st <= n; st++)
		if(g[st].size()==1)
		{
			dfsinit(st);
			dfs(st);
		}
	cout << best << " " << u[best] / 2 << endl;
	return 0;
}

/*


*/

Compilation message (stderr)

road.cpp: In function 'void dfsinit(int)':
road.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
road.cpp: In function 'void dfs(int, long long int, long long int)':
road.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~

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