Submission #93003

#	Time	Username	Problem	Language	Result	Execution time	Memory
93003		davitmarg	Hard route (IZhO17_road)	C++17	19 / 100	2060 ms	33548 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],st;
vector<int> g[N],ord;
pair<LL, LL> dp[N];
LL  best;
map<LL, int> u;
void dfsinit(int v)
{
	used[v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (used[to])
			continue;
		dfsinit(to);
		if (dp[to].first + 1 >= dp[v].first)
		{
			dp[v].second = dp[v].first;
			dp[v].first = dp[to].first + 1;
		}
		else if (dp[to].first + 1 >= dp[v].second)
			dp[v].second = dp[to].first + 1;
	}
}

void dfs(int v, LL d = 0, LL h = 0)
{
	used[v] = 1;
	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[to])
			continue;
		LL H;
		if (dp[to].first + 1 == dp[v].first)
			H = max(h,dp[v].second);
		else
			H = max(h, dp[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)
		{
			memset(dp, 0 , N * sizeof(pair<LL, LL>));
			memset(used, 0, N * sizeof(int));
			dfsinit(st);
			memset(used, 0, N * sizeof(int));
			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