oj.uz

Submission #443054

# Submission time Handle Problem Language Result Execution time Memory
443054 2021-07-09T14:48:06 Z penguinhacker Mag (COCI16_mag) C++14
120 / 120
 475 ms 92028 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 20 ms 35516 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35712 KB Output is correct
2 Correct 22 ms 35528 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 67356 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35524 KB Output is correct
2 Correct 475 ms 89560 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 73936 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 74252 KB Output is correct
2 Correct 333 ms 63980 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 75512 KB Output is correct
2 Correct 88 ms 40068 KB Output is correct
3 Correct 453 ms 92028 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 39648 KB Output is correct
2 Correct 439 ms 89600 KB Output is correct
3 Correct 441 ms 65276 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 71348 KB Output is correct
2 Correct 450 ms 73796 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 74684 KB Output is correct
2 Correct 376 ms 56012 KB Output is correct