Submission #731768

#	Time	Username	Problem	Language	Result	Execution time	Memory
731768		beaboss	Crocodile's Underground City (IOI11_crocodile)	C++14	Compilation error	0 ms	0 KiB

crocodile

#include "bits/stdc++.h"

using namespace std;

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

typedef long long ll;

typedef pair<ll, ll> pii;

const ll INF = 1e17 + 10ll;
const ll N = 2*1e5 + 10;
ll n;
vector<ll> adj[N];
ll maxoutdist[N];
ll out[N];
ll maxi = 0;
ll nummaxi = 0;
ll h[N];

void update(ll ans, ll numways) {
	if (ans > maxi) {
		maxi = ans;
		nummaxi = numways;
	} else if (ans == maxi) nummaxi += numways;
}
map<ll, vector<int>> cntheights[N];
void dfs4(ll cur, ll p) {
	for (auto val: adj[cur]) {
		if (val != p) {
			dfs4(val, cur);
			int sum = 0;
			for (auto e: cntheights[val][h[val]]) sum+=e;
			cntheights[cur][h[val] + 1].pb(sum);
		}
	}
	if (adj[cur].size() == 1) cntheights[cur][0].pb(1);
}

int numout[N];
void dfs1(ll cur, ll p) {
	vector<ll > heights;
	// map<ll, ll> cntheights;
	for (auto val: adj[cur]) {
		if (val != p) {
			heights.pb(h[val] + 1);
		}
	}


	if (out[cur] != 0) {
		heights.pb(out[cur]);
		cntheights[cur][out[cur]].pb(numout[cur]);
	}

	sort(heights.rbegin(), heights.rend());

	
	if (heights.size() >= 3) {
		cout << cur << heights[0] << heights[1] << heights[2] << endl;
		ll numways = 0;
		// cntheights[heights[0]]--;
		int sum = 0;
		if (heights[1]==heights[2]) {
			for (auto val: cntheights[cur][heights[1]]) sum += val;
			for (auto val: cntheights[cur][heights[1]]) numways += val * (sum - val);	
			numways/=2;
			// numways = (cntheights[heights[1]] * (cntheights[heights[1]] - 1ll)/2ll);
		}
		else {
			int s1 = 0;
			for (auto val: cntheights[cur][heights[1]]) s1 += val;

			int s2 = 0;
			for (auto val: cntheights[cur][heights[2]]) s2 += val;

			for (auto val: cntheights[cur][heights[1]]) numways = s1*s2;
		}

		update(heights[0] * (heights[1] + heights[2]), numways);
		// cout << numways << endl;
	}
	
	for (auto val: adj[cur]) {
		if (val != p) dfs1(val, cur);
	}
}



void dfs0(ll cur, ll p) {
	// cout << cur << endl;
	vector<ll> heights ={0, 0, 0};
	for (auto val: adj[cur]) if (val != p) heights.pb(h[val] + 2);

	sort(heights.rbegin(), heights.rend());

	for (auto val: adj[cur]) {
		if (val != p) {
			ll curopt = heights[0];
			if (h[val] + 2 == curopt) curopt = heights[1];
			if (curopt < out[cur] + 1) {
				curopt = out[cur]+1;
				numout[val] = numout[cur];
			} else if (curopt == out[cur] + 1) numout[val] += numout[cur];
			out[val] = max(out[val], curopt);
			dfs0(val, cur);
		}
	}

}


void dfs(ll cur, ll p) { // get all heights
	vector<ll> heights;
	map<ll, ll> cntheights;
	for (auto val: adj[cur]) {
		if (val != p) {
			dfs(val, cur);
			h[cur] = max(h[val] + 1, h[cur]);
		}
	}

}


int main() {
	

	cin >> n;

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

	}
	numout[1] = 1;
	dfs(1, -1);
	dfs0(1, -1);
	dfs4(1, -1);
	dfs1(1, -1);
	if (maxi == 0) nummaxi = 1;
	cout << maxi << ' ' << nummaxi << endl;



	
}

Compilation message (stderr)

crocodile.cpp: In function 'void dfs1(ll, ll)':
crocodile.cpp:79:14: warning: unused variable 'val' [-Wunused-variable]
   79 |    for (auto val: cntheights[cur][heights[1]]) numways = s1*s2;
      |              ^~~
/usr/bin/ld: /tmp/ccN0Ql3k.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccWYQhhj.o:crocodile.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccN0Ql3k.o: in function `main':
grader.cpp:(.text.startup+0x36): undefined reference to `travel_plan(int, int, int (*) [2], int*, int, int*)'
collect2: error: ld returned 1 exit status