oj.uz

답안 #873427

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873427 2023-11-15T05:16:47 Z PoPularPlusPlus Hard route (IZhO17_road) C++17
0 / 100
 5 ms 23944 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 1000000007;

const int N = 500004;

vector<int> adj[N];
vector<int> dis[N];
pair<ll,ll> ans;

void merge(ll x , ll y){
	if(x > ans.vf){
		ans = mp(x,y);
	}
	else if(x == ans.vf){
		ans.vs += y;
	}
}

int dfs(int node, int par){
	dis[node].pb(0);
	for(int i : adj[node]){
		if(i!=par){
			dis[node].pb(dfs(i,node));
		}
	}
	sort(all(dis[node]),greater<>());
	return dis[node][0] + 1;
}

void cal(int node , int par , int val , int fre){
	ll mx = dis[node][0];
	ll cnt = 1;
	for(int i = 1; i < dis[node].size(); i++){
		if(dis[node][i] == mx)cnt++;
		else break;
	}
	ll mx1 = -1 , cnt1 = 0;
	if(cnt == 1){
		mx1 = 0;
		if(dis[node].size() > 1){
			mx1 = dis[node][1];
			for(int i = 1; i < dis[node].size(); i++){
				if(dis[node][i] == mx1)cnt1++;
				else break;
			}
		}
	}
	if(val > mx){
		swap(mx,mx1);
		swap(cnt,cnt1);
		mx = val;
		cnt = fre;
	}
	else if(val == mx){
		cnt += fre;
	}
	else if(val > mx1){
		mx1 = val;
		cnt1 = fre;
	}
	else if(val == mx1){
		cnt1 += fre;
	}

	for(int i : adj[node]){
		if(i!=par){
			if(dis[i][0] + 1 == mx){
				if(cnt==1){
					cal(i,node,mx1+1,cnt1);
				}
				else {
					cal(i,node,mx+1,cnt-1);
				}
			}
		}
	}

	if(dis[node].size() <= 2)return;
	ll x = dis[node][0];
	ll y = dis[node][1];
	ll yf = 1;
	for(int i = 2; i < dis[node].size(); i++){
		if(dis[node][i] != yf)break;
		yf++;
	}
	if(x != y){
		merge((x+y)*val,fre*yf);
		merge((x+val)*y,fre*yf);
		merge((y+val)*x,fre*yf);
	}
	else {
		yf++;
		merge((x+y)*val,fre*((yf*(yf-1LL))/2));
		merge((x+val)*y,fre*((yf*(yf-1LL))/2));
		merge((y+val)*x,fre*((yf*(yf-1LL))/2));
	}
}

void solve(){
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		int a , b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}

	dfs(1,1);
	ans=mp(0,1);
	cal(1,1,0,0);
	cout << ans.vf << ' ' << ans.vs << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int t;cin>>t;
	//while(t--)
		solve();
	return 0;
}

Compilation message

road.cpp: In function 'void cal(int, int, int, int)':
road.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i = 1; i < dis[node].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~
road.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    for(int i = 1; i < dis[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
road.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(int i = 2; i < dis[node].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Correct 5 ms 23900 KB Output is correct
3 Correct 5 ms 23944 KB Output is correct
4 Incorrect 5 ms 23900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Correct 5 ms 23900 KB Output is correct
3 Correct 5 ms 23944 KB Output is correct
4 Incorrect 5 ms 23900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Correct 5 ms 23900 KB Output is correct
3 Correct 5 ms 23944 KB Output is correct
4 Incorrect 5 ms 23900 KB Output isn't correct
5 Halted 0 ms 0 KB -