Submission #443054

#	Time	Username	Problem	Language	Result	Execution time	Memory
443054		penguinhacker	Mag (COCI16_mag)	C++14	120 / 120	475 ms	92028 KiB

mag

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e6;
int n, a[mxN], d1[mxN], d2[mxN], d3[mxN], dp[mxN];
vector<int> adj[mxN];

int bfs(int s, int d[]) {
	d[s]=0;
	vector<int> q={s};
	for (int i=0; i<q.size(); ++i) {
		int u=q[i];
		for (int v : adj[u])
			if (a[v]==1&&d[v]==-1) {
				d[v]=d[u]+1;
				q.push_back(v);
			}
	}
	return q.back();
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i=0; i<n; ++i)
		cin >> a[i];
	if (*min_element(a, a+n)>1) {
		cout << *min_element(a, a+n) << "/1";
		return 0;
	}
	memset(d1, -1, sizeof(d1));
	memset(d2, -1, sizeof(d2));
	memset(d3, -1, sizeof(d3));
	for (int i=0; i<n; ++i)
		if (d1[i]==-1&&a[i]==1) {
			int u=bfs(i, d1);
			int v=bfs(u, d2);
			bfs(v, d3);
		}
	for (int i=0; i<n; ++i)
		if (d2[i]^-1)
			dp[i]=max(d2[i], d3[i])+1;
	ar<int, 2> ans={1, *max_element(dp, dp+n)};
	for (int i=0; i<n; ++i)
		if (a[i]==2) {
			ar<int, 2> b={-1, 0};
			for (int j : adj[i])
				if (a[j]==1&&dp[j]>=b[0]) {
					if (dp[j]>b[0])
						b={dp[j], 1};
					else
						++b[1];
				}
			if (b[0]^-1&&b[1]>=2)
				if (2*ans[1]<(2*b[0]+1)*ans[0])
					ans={2, 2*b[0]+1};
		}
	cout << ans[0] << "/" << ans[1];
	return 0;
}

Compilation message (stderr)

mag.cpp: In function 'int bfs(int, int*)':
mag.cpp:14:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for (int i=0; i<q.size(); ++i) {
      |                ~^~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12