Submission #731099

#	Time	Username	Problem	Language	Result	Execution time	Memory
731099		beaboss	Hard route (IZhO17_road)	C++14	19 / 100	2069 ms	5652 KiB

road

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
const ll N = 2*1e5 + 10;

vector<ll> adj[N];
bool v[N];
bool visited[N];
int curdist = 0;
int maxd = 0;
ll maxi = 0;
ll nummaxi = 0;

void update(ll ans, ll numways) {
	if (ans > maxi) {
		maxi = ans;
		nummaxi = numways;
	} else if (ans == maxi) nummaxi += numways;
}

bool dfs(int cur, int target, int d) {
	if (cur == target) {
		v[cur]=true;
		curdist = d;
		return true;
	}
	// cout << cur << target << endl;
	visited[cur]=true;
	for (auto val: adj[cur]) {
		if (!visited[val]) {

			v[cur] = (dfs(val, target, d+ 1) || v[cur]);
		}
	}
	return v[cur];
}



void dfs2(int cur, int d) {
	visited[cur] = true;
	if (d > maxd) {
		maxd = d;
		// update(curdist * d, 1);
	}

	for (auto val: adj[cur]) {
		if (!visited[val] && !v[val]) dfs2(val, d+1);
	}
}


int main() {
	int n;
	cin >> n;

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

	}
	vector<int> leaves;
	for (int i = 1; i <= n; i++) {
		if (adj[i].size() == 1) {
			leaves.push_back(i);
		}
	}

	for (int i = 0; i < leaves.size(); i++) {
		for (int j = i + 1; j < leaves.size(); j++) {
			int curans = 0;
			maxd = 0;
			curdist = 0;
			memset(v, false, sizeof v);
			memset(visited, false, sizeof visited);
			dfs(leaves[i], leaves[j], 0);
			memset(visited, false, sizeof visited);
			for (int i = 0; i < n; i++) {
				if (v[i]) {

					dfs2(i, 0);
				}
			}

			// cout << leaves[i] << leaves[j] << curdist << maxd << endl;
			update(curdist * maxd, 1);

		}
	}
	cout << maxi << ' ' << nummaxi << endl;
}

Compilation message (stderr)

road.cpp: In function 'int main()':
road.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < leaves.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
road.cpp:80:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int j = i + 1; j < leaves.size(); j++) {
      |                       ~~^~~~~~~~~~~~~~~
road.cpp:81:8: warning: unused variable 'curans' [-Wunused-variable]
   81 |    int curans = 0;
      |        ^~~~~~

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