Submission #246299

#TimeUsernameProblemLanguageResultExecution timeMemory
246299Vladikus004Mag (COCI16_mag)C++14
120 / 120
674 ms239756 KiB
#include <bits/stdc++.h> #define int long long //#pragma comment(linker, "/STACK:6666777216") #define inf 2e9 #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef long double ld; typedef pair <int, int> pii; const int N = 1000000 + 3; int n, z[N], p[N], udp[N], ddp[N]; vector <vector <int> > v, mx; void udfs(int x){ p[x] = 1; // cout << x << " " << v[x].size() << "\n"; // cout << p[v[x][0]] << " " << p[v[x][1]] << "!!!\n"; // if ( x == 432518) { // exit(0); // } for (auto u: v[x]){ if (p[u]) continue; udfs(u); mx[x].push_back(udp[u]); udp[x] = max(udp[x], udp[u]); } if (z[x] == 1) udp[x]++; else udp[x] = 0; if (mx[x].size()){ sort(all(mx[x])); reverse(all(mx[x])); } } int ans; int e_ans; int mn = inf * inf; void ddfs(int x, int way){ p[x] = 1; mn = min(mn, z[x]); e_ans = max(e_ans, way); if (z[x] == 2){ if (!mx[x].empty()){ vector <int> buff; buff.push_back(way); buff.push_back(mx[x][0]); if (mx[x].size() > 1) buff.push_back(mx[x][1]); sort(all(buff)); ans = max(ans, buff[(buff.size() - 1) / 2] * 2 + 1); } } for (auto u: v[x]){ if (p[u]) continue; if (z[x] != 1) { ddfs(u, 0); continue; } e_ans = max(e_ans, udp[u]); if (udp[u] == mx[x][0]){ if (mx[x].size() > 1) ddfs(u, max(way + 1, mx[x][1] + 1)); else ddfs(u, way + 1); }else{ ddfs(u, max(way + 1, mx[x][0] + 1)); } } if (mx[x].size()){ int t = mx[x][0]; if (mx[x].size() > 1) t += mx[x][1]; if (z[x] == 1) e_ans = max(e_ans, t + 1); } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // LOCAL cin >> n; v.resize(n); mx.resize(n); for (int i = 0; i < n - 1; i++){ int a, b; cin >> a >> b; --a; --b; v[a].push_back(b); v[b].push_back(a); } for (int i = 0; i < n; i++) cin >> z[i]; udfs(0); memset(p, 0, sizeof p); ddfs(0, 0); // assert(ans != 799997); if (ans){ if (e_ans * 2 < ans) cout << "2/"<<ans; else cout << "1/"<<e_ans; }else if (e_ans){ cout << "1/"<<e_ans; }else cout << mn<<"/1"; }
#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...