제출 #1116107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116107		hamzabc	Hard route (IZhO17_road)	C++14	0 / 100	1 ms	336 KiB

road

#include <bits/stdc++.h>
 
 
using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'

vector<vector<int>> graph;
vector<long long int> dist;
vector<long long int> distind;
vector<long long int> distmul;
long long int hard = 0;
long long int cnt = 0;
int n;



void dp(int node = 0, int parent = -1){
	for (auto go : graph[node]){
		if (go == parent)
			continue;
		dp(go, node);
		if (dist[node] < dist[go] + 1){
			dist[node] = dist[go] + 1;
			distmul[node] = distmul[go];
		}else if (dist[node] == dist[go] + 1){
			distmul[node] += distmul[go];
		}
	}
}

void reroot(int node = 0, int parent = -1, long long int parentdist = -1, long long int parentmul = 1){
	long long int big1 = parentdist + 1, big2 = 0, big3 = 0;
	long long int mul1 = parentmul, mul2 = 0, mul3 = 0;
	for (int go : graph[node]){
		if (go == parent)
			continue;
		if (dist[go] + 1 > big1){
			big3 = big2;
			mul3 = mul2;
			big2 = big1;
			mul2 = mul1;
			big1 = dist[go] + 1;
			mul1 = distmul[go];
		}else if (dist[go] + 1 > big2){
			big3 = big2;
			mul3 = mul2;
			big2 = dist[go] + 1;
			mul2 = distmul[go];
		}else if (dist[go] + 1 > big3){
			big3 = dist[go] + 1;
			mul3 = distmul[go];
		}
	}
	long long int deg1 = big1 * (big2 + big3);
	if (graph[node].size() > 2 && deg1 > hard){
		hard = deg1;
	}
	for (int go : graph[node]){
		if (go == parent)
			continue;
		if (big1 == dist[go] + 1){
			reroot(go, node, big2, mul2);
		}else{
			reroot(go, node, big1, mul1);
		}
	}
}

void reroot2(int node = 0, int parent = -1, long long int parentdist = -1, long long int parentmul = 1, bool parentused = false){
	if (graph[node].size() == 0)
		return;
	long long int big1 = parentdist + 1, big2 = 0, big3 = 0;
	long long int mul1 = parentmul, mul2 = 0, mul3 = 0;
	if (parentused){
		big1 = 0;
		mul1 = 0;
	}
	for (int go : graph[node]){
		if (go == parent)
			continue;
		if (dist[go] + 1 > big1){
			big3 = big2;
			mul3 = mul2;
			big2 = big1;
			mul2 = mul1;
			big1 = dist[go] + 1;
			mul1 = distmul[go];
		}else if (dist[go] + 1 > big2){
			big3 = big2;
			mul3 = mul2;
			big2 = dist[go] + 1;
			mul2 = distmul[go];
		}else if (dist[go] + 1 > big3){
			big3 = dist[go] + 1;
			mul3 = distmul[go];
		}
	}
	long long int deg1 = big1 * (big2 + big3), deg2 = big2 * (big1 + big3), deg3 = big3 * (big2 + big1);
	bool flag1 = false, flag2 = false;
	if (deg1 == hard){
		if (deg2 == deg1 && deg2 == deg3){
			cnt += mul1 * mul2 + mul2 * mul3 + mul3 * mul1;
			flag2 = true;
			flag1 = true;
		}else if (deg1 == deg2){
			cnt += mul2 * mul3 + mul1 * mul3;
			flag2 = true;
			flag1 = true;
		}else{
			cnt += mul2 * mul3;
			flag1 = true;
		}
	}else if (parentused && (big1 + big2) * (parentdist + 1) == hard){
		cnt += mul2 * mul1;
		flag1 = true;
		flag2 = true;
	}
	for (int go : graph[node]){
		if (go == parent)
			continue;
		if (parentused){
			if (big1 != dist[go] + 1 && big1 >= parentdist)
				reroot2(go, node, big1, mul1, flag2);
			else if (big2 >= parentdist)
				reroot2(go, node, big2, mul2, flag1);
			else
				reroot2(go, node, parentdist + 1, parentmul, true);
		}else{
			if (big1 == dist[go] + 1)
				reroot2(go, node, big2, mul2, flag1);
			else
				reroot2(go, node, big1, mul1, flag2);
		}
	}
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	graph.resize(n);
	dist.resize(n, 0);
	distind.resize(n);
	distmul.resize(n, 1);
	for (int i = 0; i < n - 1; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	dp();
	reroot();
	reroot2();
	cout << hard sp cnt;
}

컴파일 시 표준 에러 (stderr) 메시지

road.cpp: In function 'void reroot(int, int, long long int, long long int)':
road.cpp:38:44: warning: variable 'mul3' set but not used [-Wunused-but-set-variable]
   38 |  long long int mul1 = parentmul, mul2 = 0, mul3 = 0;
      |                                            ^~~~

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