Submission #341280

#	Time	Username	Problem	Language	Result	Execution time	Memory
341280		Tosic	Hard route (IZhO17_road)	C++14	52 / 100	595 ms	64260 KiB

road

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

int n, ans, cnt, maxO[maxn], iT[maxn], oT[maxn], gT;
vector<int> dp[maxn];
vector<vector<int>> gr;

void dfs(int x, int p){
	iT[x] = gT;
	++gT;
	dp[x].push_back(0);
	for(auto i:gr[x]){
		if(i ==p){
			continue;
		}
		dfs(i, x);
		dp[x].push_back(dp[i].back()+1);
	}
	sort(dp[x].begin(), dp[x].end());
	oT[x] = gT;
	++gT;
}

void dfs1(int cur, int p, int x, int d){
	if(iT[cur] > iT[x] and oT[cur] < oT[x]){
		return;
	}
	maxO[x] = max(maxO[x], d);
	
	
	for(auto i : gr[cur]){
		if(i==p){
			continue;
		}
		dfs1(i, cur, x, d+1);
	}
}

bool isA(int x, int y){
	return iT[x] < iT[y];
}

bool isL(int x){
	return gr[x].size()==1;
}

void cDfs(int x, int p, bool up, int d, int res){
	if(p != -1 and isL(x)){
		if(ans == d*res){
			++cnt;
		}
		if(ans < d*res){
			cnt = 1;
			ans = d*res;
		}
		return;
	}
	for(auto i : gr[x]){
		if(i != p){
			if(isA(x, i) and up){
				int idx = int(dp[x].size())-1;
				if(dp[x][idx] == max(dp[i].back()+1,dp[p].back()+1) ){
					--idx;
				}
				if(dp[x][idx] == min(dp[p].back()+1,dp[i].back()+1) ){
					--idx;
				}
				int tmpRes = max(res, dp[x][idx]);
				tmpRes = max(tmpRes, maxO[x]);
				cDfs(i, x, 0, d+1, tmpRes);
			} else {
				int idx = int(dp[x].size())-1, tmpRes;
				if(up){
					if(p >= 0 and dp[x][idx] == dp[p].back()+1){
						--idx;
					}
					tmpRes = max(res, dp[x][idx]);
				} else {
					if(dp[x][idx] == dp[i].back()+1){
						--idx;
					}
					tmpRes = max(res, dp[x][idx]);
				}
				cDfs(i, x, up, d+1, tmpRes);
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n;
	gr.resize(n, vector<int>());
	for(int i = 0; i < n-1; ++i){
		int u, v;
		cin >> u >> v;
		--u,--v;
		gr[u].push_back(v);
		gr[v].push_back(u);
	}
	if(n == 2){
		cout << "0 1";
		return 0;
	}
	for(int i = 0; i < n; ++i){
		if(!isL(i)){
			dfs(i, -1);
			break;
		}
	}
	for(int i = 0; i < n; ++i){
		dfs1(i, -1, i, 0);
	}
	for(int i = 0; i < n; ++i){
		if(isL(i)){
			cDfs(i, -1, 1, 0, 0);
		}
	}
	cout<<ans<<' '<<cnt/2<<'\n';
}

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