oj.uz

Submission #99122

# Submission time Handle Problem Language Result Execution time Memory
99122 2019-02-28T19:08:34 Z luciocf Mag (COCI16_mag) C++14
0 / 120
 1323 ms 263168 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6+10;

int num[maxn], P=-1, Q=-1;

int dp_down[maxn], dp_up[maxn];

vector<int> grafo[maxn];

void dfs_down(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v == p) continue;

		dfs_down(v, u);

		if (num[v] == 1) 
			dp_down[u] = max(dp_down[u], dp_down[v]+1);
	}
}

void dfs_up(int u, int p)
{
	int tam = (int)grafo[u].size();
	vector<int> pref, suf;

	pref.resize(tam+2);
	suf.resize(tam+2);
	pref[0] = suf[tam+1] = 0;

	for (int i = 1; i <= tam; i++)
	{
		int v = grafo[u][i-1];
		if (v == p) continue;

		pref[i] = pref[i-1];
		if (num[v] == 1) pref[i] = max(pref[i], dp_down[v]+1);
	}

	for (int i = tam; i >= 1; i--)
	{
		int v = grafo[u][i-1];
		if (v == p) continue;

		suf[i] = suf[i+1];
		if (num[v] == 1) suf[i] = max(suf[i], dp_down[v]+1);
	}

	int m1 = dp_up[u], m2 = 0, ans = 0;
	for (int i = 1; i <= tam; i++)
	{
		int v = grafo[u][i-1];
		if (v == p) continue;

		if (num[v] == 1)
		{
			if (dp_down[v]+1 > m1) m2 = m1, m1 = dp_down[v]+1;
			else if (dp_down[v]+1 > m2) m2 = dp_down[v]+1;
		}

		if (num[u] == 1)
			dp_up[v] = max({dp_up[u], pref[i-1], suf[i+1]})+1;
		else dp_up[v] = 0;

		ans = max(ans, m1+m2+1);

		dfs_up(v, u);
	}

	long long A = 1ll*num[u]*1ll*Q;
	long long B = 1ll*ans*1ll*P;

	if (P == -1 || A > B) P = num[u], Q = ans;
}

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

	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;

		grafo[u].push_back(v); grafo[v].push_back(u);
	}

	for (int i = 1; i <= n; i++)
		cin >> num[i];

	dfs_down(1, 0); dfs_up(1, 0);

	int g = __gcd(P, Q);

	cout << P / g << "/" << Q / g << "\n";
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1304 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #6
0 / 12.0

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

Subtask #7
0 / 12.0

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

Subtask #8
0 / 12.0

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

Subtask #9
0 / 12.0

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

Subtask #10
0 / 12.0

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