oj.uz

Submission #443051

# Submission time Handle Problem Language Result Execution time Memory
443051 2021-07-09T14:34:32 Z penguinhacker Mag (COCI16_mag) C++14
48 / 120
 567 ms 92848 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];
bool vis[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 (!vis[i]&&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 (dp[j]&&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:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for (int i=0; i<q.size(); ++i) {
      |                ~^~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 18 ms 35532 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 35596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 81220 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 35532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 546 ms 90776 KB Output isn't correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 89692 KB Output is correct
2 Correct 393 ms 75216 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 92848 KB Output is correct
2 Incorrect 103 ms 41584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 40944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 86964 KB Output is correct
2 Correct 567 ms 91060 KB Output is correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 90052 KB Output is correct
2 Incorrect 480 ms 63364 KB Output isn't correct