Submission #1081566

#TimeUsernameProblemLanguageResultExecution timeMemory
1081566vjudge1Mag (COCI16_mag)C++17
84 / 120
893 ms262144 KiB
#include<bits/stdc++.h> using namespace std; bool operator < (const pair<int, int>& x, const pair<int, int>& y) { return 1LL * x.first * y.second < 1LL * x.second * y.first; } int main() { int n; cin >> n; vector<vector<int>> adj(n + 1, vector<int>()); for (int i = 1, a, b; i < n; i++) { cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } vector<int> val(n + 1, 0); vector<vector<int>> dp(n + 1, vector<int>()), dp_pref(n + 1, vector<int>()), dp_suf(n + 1, vector<int>()); vector<int> dp2(n + 1, 0); for (int i = 1; i <= n; i++) cin >> val[i]; function<void(int, int)> dfs1 = [&](int u, int par) -> void { if (u != 1 && adj[u].size() == 1) { dp[u].emplace_back(0); dp_pref[u].emplace_back(0); dp_suf[u].emplace_back(0); return; } for (int v: adj[u]) { if (v == par) { dp[u].push_back(0); continue; } dfs1(v, u); if (val[v] != 1) dp[u].push_back(0); else dp[u].push_back(dp_suf[v][1] + 1); } int k = adj[u].size(); dp_pref[u].assign(k + 2, 0); dp_suf[u].assign(k + 2, 0); for (int j = 1; j <= k; j++) dp_pref[u][j] = max(dp_pref[u][j - 1], dp[u][j - 1]); for (int j = k; j >= 1; j--) dp_suf[u][j] = max(dp_suf[u][j + 1], dp[u][j - 1]); }; dfs1(1, 0); function<void(int, int)> dfs2 = [&](int u, int par) { if (u != 1 && adj[u].size() == 1) return; int k = adj[u].size(); for (int j = 1; j <= k; j++) { if (adj[u][j - 1] == par) continue; int v = adj[u][j - 1]; if (val[u] != 1) dp2[v] = 0; else dp2[v] = max(dp2[u], max(dp_pref[u][j - 1], dp_suf[u][j + 1])) + 1; dfs2(v, u); } }; dfs2(1, 0); pair<int, int> ans = {1e9 + 7, 1}; for (int i = 1; i <= n; i++) { pair<int, int> tmp = {val[i], dp_suf[i][1] + dp2[i] + 1}; if (tmp < ans) ans = tmp; } int g = __gcd(ans.first, ans.second); ans.first /= g; ans.second /= g; cout << ans.first << '/' << ans.second; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...