oj.uz

Submission #99127

# Submission time Handle Problem Language Result Execution time Memory
99127 2019-02-28T19:20:11 Z luciocf Mag (COCI16_mag) C++14
120 / 120
 1426 ms 237176 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6+5;

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(tam+2), suf(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;

		dfs_up(v, u);
	}

	ans = m1+m2+1;

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

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24064 KB Output is correct
2 Correct 24 ms 23936 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23808 KB Output is correct
2 Correct 26 ms 23936 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1180 ms 120992 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23808 KB Output is correct
2 Correct 1386 ms 237176 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1403 ms 231280 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1271 ms 66740 KB Output is correct
2 Correct 915 ms 67192 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1158 ms 70456 KB Output is correct
2 Correct 210 ms 29816 KB Output is correct
3 Correct 1426 ms 233820 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 28328 KB Output is correct
2 Correct 1198 ms 83468 KB Output is correct
3 Correct 1004 ms 53736 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 66576 KB Output is correct
2 Correct 1222 ms 78968 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1176 ms 67780 KB Output is correct
2 Correct 1057 ms 53652 KB Output is correct