oj.uz

Submission #92998

# Submission time Handle Problem Language Result Execution time Memory
92998 2019-01-06T09:48:04 Z davitmarg Hard route (IZhO17_road) C++17
0 / 100
 2 ms 508 KB 
/*
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;
		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

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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Incorrect 2 ms 504 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Incorrect 2 ms 504 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Incorrect 2 ms 504 KB Output isn't correct
8 Halted 0 ms 0 KB -