Submission #37240

#	Time	Username	Problem	Language	Result	Execution time	Memory
37240		temurbek_khujaev	Hard route (IZhO17_road)	C++14	0 / 100	9 ms	16648 KiB

road

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <math.h>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <string.h>
#include <cstring>
#include <queue>
#include <iomanip>
#include <istream>
#include <map>
#include <list>
#include <stack>
#include <numeric>
#include <ostream>
#include <set>
#include <cassert>
#include <sstream>
#include <string>
#include <utility>
#include <stdio.h>
#include <vector>
using namespace std;
#define dout if (debug) cout
#define PB push_back
#define MP make_pair
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int((x.size())))
typedef long double ld;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<PII> VPI;
#define REP(i,a,n) for (int i=a;i<n;i++)
#define db(x) cerr << #x << " = " << x << endl
#define PER(i,a,n) for (int i=n-1;i>=a;i--)
const int INF = 1000000404;
const ll MOD = 1000000007ll;
const ld PI = acos(-1.0);
const ld EPS = 1e-9;
template <typename t1, typename t2> inline void upmax(t1 &a, t2 b) { a = max(a, (t1)b); }
template <typename t1, typename t2> inline void upmin(t1 &a, t2 b) { a = min(a, (t1)b); }
template <typename T>inline T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }
template <typename T>inline T lcm(T a, T b) { return a*(b / gcd(a, b)); }
template <typename T>inline T sqr(T a) { return a*a; }
template <typename T>inline bool pal(T &x)
{
	int n = SZ(x); REP(i, 0, n / 2) { if (x[i] != x[n - i - 1]) return 0; }return 1;
}
template <typename T>inline void rev(T &x) { int n = SZ(x); REP(i, 0, n / 2) swap(x[i], x[n - i - 1]); }
int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dy[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
inline ll mp(ll a, ll b) { return (a << 31) + b; }
class compare{
public:
	bool operator()(const int a, const int b) const {
		return 1;
	}
};
int SQ = 400;

#define debug 1
#define N 511111
VI g[N];
int d[N];
bool used[N];
int n;
void DFS(int v) {
	used[v] = true;
	for (auto x : g[v]) {
		if (!used[x]) {
			d[x] = d[v] + 1;
			DFS(x);
		}
	}
}

int depth(int v, int p = -1, int h = 1) {
	int ret = h;
	for (auto x : g[v]){
		if (x != p) upmax(ret, depth(x, v, h + 1));
	}
	return ret;
}
int crossed_depth(int v,int need, int p = -1, int h = 1) {
	if (h == need) return 1;	
	int cnt = 0;
	for (auto x : g[v]){
		if (x != p) cnt += crossed_depth(x, need, v, h + 1);
	}
	return cnt;
}


void solve()
{
	cin >> n;
	REP(i, 1, n) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	// diameter
	fill(used, used + N, false);
	d[1] = 0;
	DFS(1);
	int x = 1;
	REP(i, 1, n + 1) if (d[i] > d[x]) x = i;

	fill(used, used + N, false);
	d[x] = 0;
	DFS(x);
	int y = 1;
	REP(i, 1, n + 1) if (d[i] > d[y]) y = i;
	VI path;
	int v = y;
	while (x != v) {
		path.push_back(v);
		for (auto from : g[v]) {
			if (d[from] < d[v]) {
				v = from;
				break;
			}
		}
	}
	path.push_back(x);
	db(x);	db(y);
//	cout << "PATH: "; for (auto x : path) cout << x << ' '; cout << endl;

	ll maxans= 0;
	ll cntans = 0;
	ll a, b, c;
	REP(i, 1, SZ(path) - 1) {
		a = i;
		b = SZ(path) - a - 1;

		int v = path[i];
		int prv = path[i - 1];
		int nxt = path[i + 1];
		ll maxx = 0;
		ll cnt = 0;

		for (auto to : g[v]) {
			if (to == prv || to == nxt) continue;
			int h = depth(to, v);
			upmax(maxx, h);
		}
		c = maxx;

		upmax(maxans, (a + b)*c);
		if (c != 0) upmax(maxans, max((a + c)*b, (b + c)*a));
	}
	db(maxans);
	int plusone = 0;
	REP(i, 1, SZ(path) - 1) {
		a = i;
		b = SZ(path) - a - 1;

		int v = path[i];
		int prv = path[i - 1];
		int nxt = path[i + 1];
		ll maxx = 0;
		ll cnt = 0;
		ll cd = 0;
		for (auto to : g[v]) {
			if (to == prv || to == nxt) continue;
			int h = depth(to, v);
			if (h > maxx) {
				maxx = h;
				cnt = 1;
			}
			else {
				if (maxx == h) 	cnt++;
			}
		}

		for (auto to : g[v]) {
			if (to == prv || to == nxt) continue;
			cd += crossed_depth(to, maxx, v);
		}
		c = maxx;

		//db(c);		db(cnt);		db(cd);
		if ((a + b)*c == maxans) plusone = 1;

		if (c != 0 && (b + c)*a == maxans) {
			if (c < b) cntans += cd; else {
				cntans += (cnt*(cnt + 1)) / 2;
			}
		}
		if (c != 0 && (a + c)*b == maxans) {
			if (c < a) cntans += cd; else {
				cntans += (cnt*(cnt + 1)) / 2;
			}
		}
	}
	cout << maxans << ' ' << max(1ll,cntans+plusone);
}

int main()
{
	ios_base::sync_with_stdio(false);	cin.tie(0);	cout.tie(0);
	int t = 1;
	//cin>>t;

	while (t--) {
		solve();
	};


	getchar();
	getchar();
	return 0;
}

Compilation message (stderr)

road.cpp: In function 'void solve()':
road.cpp:149:6: warning: unused variable 'cnt' [-Wunused-variable]
   ll cnt = 0;
      ^

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