Submission #92540

#	Time	Username	Problem	Language	Result	Execution time	Memory
92540		Just_Solve_The_Problem	Hard route (IZhO17_road)	C++11	52 / 100	1120 ms	88900 KiB

road

#include <bits/stdc++.h>
 
using namespace std;

#define ll long long

const int N = (int)5e5 + 7;

int n;

pair < int, int > refresh(pair < int, int > A, pair < int, int > B) {
	if (A.first < B.first) {
		return B;
	} else if (A.first > B.first) {
		return A;
	} else {
		return {A.first, A.second + B.second};
	}
}

struct T {
	pair < int, int > tree[4 * N];
	T() {
	}
	void upd(int pos, int val, int v = 1, int l = 1, int r = n) {
		if (l == r) {
			tree[v] = {val, 1};
			return ;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) {
			upd(pos, val, v + v, l, mid);
		} else {
			upd(pos, val, v + v + 1, mid + 1, r);
		}
		tree[v] = refresh(tree[v + v], tree[v + v + 1]);
	}
	
	pair < int, int > getmax(int l, int r, int v = 1, int tl = 1, int tr = n) {
		if (tl > r || tr < l) return {0, 0};
		if (l <= tl && tr <= r) return tree[v];
		int mid = (tl + tr) >> 1;
		return refresh(getmax(l, r, v + v, tl, mid), getmax(l, r, v + v + 1, mid + 1, tr));
	}
};
T tr;

vector < int > gr[N];
int tin[N], tout[N], tiktak;
int h[N];
pair < ll, ll > ans, ans1;
pair < int, int > asd;

void dfs(int v, int pr) {
	tin[v] = ++tiktak;
	tr.upd(tin[v], h[v]);
	for (int to : gr[v]) {
		if (to == pr) continue;
		h[to] = h[v] + 1;
		dfs(to, v);
	}
	tout[v] = tiktak;
}

void dfs1(int v, int pr, pair < int, int > mxx, pair < int, int > asd) {
	pair < int, int > fir, sec;
	for (int to : gr[v]) {
		if (to == pr) continue;
		pair < int, int > res = mxx;
		pair < int, int > asd1 = asd;
		fir = tr.getmax(tin[to], tout[to]);
		sec = refresh(tr.getmax(tin[v] + 1, tin[to] - 1), tr.getmax(tout[to] + 1, tout[v]));
		sec.first -= h[v];
		fir.first -= h[v];
		if (mxx.first > 0) {
			if (sec.first > 0) {
				if ((fir.first + sec.first) * 1LL * mxx.first > ans.first) {
					ans.first = (fir.first + sec.first) * 1LL * mxx.first;
					ans.second = fir.second * 1LL * sec.second;
				} else if ((fir.first + sec.first) * 1LL * mxx.first == ans.first) {
					ans.second += fir.second * 1LL * sec.second;
				}
				if ((fir.first + mxx.first) * 1LL * sec.first > ans1.first) {
					ans1.first = (fir.first + mxx.first) * 1LL * sec.first;
					ans1.second = fir.second * 1LL * mxx.second;
					asd1.first = h[v] + fir.first;
					asd1.second = mxx.second;
				} else if ((fir.first + mxx.first) * 1LL * sec.first == ans1.first) {
					if (fir.first + h[v] == asd1.first) {
						ans1.second += fir.second * 1LL * (mxx.second - asd1.second);
					} else {
						ans1.second += fir.second * 1LL * mxx.second;
						asd1.first = fir.first + h[v];
					}
					asd1.second = mxx.second;
				}
			}
		}
		if (res.first < sec.first) {
			asd1 = {-1, 0};
		}
		res = refresh(res, sec);
		res.first++;
		dfs1(to, v, res, asd1);
	}
}

main() {
	//freopen("road.in", "r", stdin);
	//freopen("road.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		gr[u].push_back(v);
		gr[v].push_back(u);
	}
	ans = ans1 = {0, 1};
	dfs(1, 1);
	dfs1(1, 1, {0, 1}, {-1, 0});
	ans.second /= 2;
	ans = refresh(ans, ans1);
	cout << ans.first << ' ' << ans.second;
}
/*
8
1 2
2 3
3 4
2 5
5 6
6 8
5 7
*/

Compilation message (stderr)

road.cpp:108:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
road.cpp: In function 'int main()':
road.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
road.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

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