Submission #1115168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115168		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, int parentind = -1){
	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;
	long long int ind1 = parentind, ind2 = -1, ind3 = -1;
	for (int go : graph[node]){
		if (go == parent)
			continue;
		if (dist[go] + 1 > big1){
			big3 = big2;
			mul3 = mul2;
			ind3 = ind2;
			big2 = big1;
			mul2 = mul1;
			ind2 = ind1;
			big1 = dist[go] + 1;
			mul1 = distmul[go];
			ind1 = distind[go];
		}else if (dist[go] + 1 > big2){
			big3 = big2;
			mul3 = mul2;
			ind3 = ind2;
			big2 = dist[go] + 1;
			mul2 = distmul[go];
			ind2 = distind[go];
		}else if (dist[go] + 1 > big3){
			big3 = dist[go] + 1;
			mul3 = distmul[go];
			ind3 = distind[go];
		}
	}
	long long int deg1 = big1 * (big2 + big3), deg2 = big2 * (big1 + big3), deg3 = big3 * (big2 + big1);
	if (deg1 == hard){
		if (deg2 == deg1 && deg2 == deg3){
			cnt += mul1 * mul2 + mul2 * mul3 + mul3 * mul1;
			mul1 = 0;
			big1 = 0;
			mul2 = 0;
			big2 = 0;
			mul3 = 0;
			big3 = 0;
		}else if (deg1 == deg2){
			cnt += mul2 * mul3 + mul1 * mul3;
			mul1 = 0;
			big1 = 0;
			mul2 = 0;
			big2 = 0;
			mul3 = 0;
			big3 = 0;
		}else{
			cnt += mul2 * mul3;
			big2 = 0;
			mul2 = 0;
			big3 = 0;
			mul3 = 0;
		}
	}
	for (int go : graph[node]){
		if (go == parent)
			continue;
		if (big1 == dist[go] + 1)
			reroot2(go, node, big2, mul2, ind2);
		else
			reroot2(go, node, big1, mul1, ind1);
	}
}


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;
}

Compilation message (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;
      |                                            ^~~~
road.cpp: In function 'void reroot2(int, int, long long int, long long int, int)':
road.cpp:79:45: warning: variable 'ind3' set but not used [-Wunused-but-set-variable]
   79 |  long long int ind1 = parentind, ind2 = -1, ind3 = -1;
      |                                             ^~~~

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