Submission #286532

#TimeUsernameProblemLanguageResultExecution timeMemory
286532FlashGamezzzMag (COCI16_mag)C++11
84 / 120
565 ms262148 KiB
#include <iostream> #include <cstdlib> #include <cstdio> #include <fstream> #include <algorithm> #include <string> #include <utility> #include <vector> using namespace std; long n, minM = 1000000000, maxP = 0, mag[1000000], pd[1000000] = {}, path[1000000] = {}, pn[1000000] = {}; vector <long> adj[1000000], mi[1000000]; void dfs(int i, int p) { minM = min(minM, mag[i]); for (int a : adj[i]) { if (a != p) { dfs(a, i); } } if (mag[i] == 1) { pd[i] = 1; for (int a : adj[i]) { if (a != p && mag[a] == 1) { if (pd[a]+1 > pd[i]) { pd[i] = pd[a]+1; vector <long> t; t.push_back(a); mi[i] = t; } else if (pd[a]+1 == pd[i]) { mi[i].push_back(a); } } } path[i] = pd[i]; if (mi[i].size() == 1){ long mind = mi[i][0]; vector <long> t; for (int a : adj[i]){ if (a != p && mag[a] == 1 && a != mind ) { if (pd[i]+pd[a] > path[i]){ path[i] = pd[i]+pd[a]; vector <long> tt; tt.push_back(a); t = tt; } else if (pd[i]+pd[a] == path[i]){ t.push_back(a); } } } for (int a : t){ mi[i].push_back(a); } } else if (mi[i].size() > 1){ path[i] = 2*pd[i]-1; } maxP = max(path[i], maxP); } } void dfs2(int i, int v){ pn[i] = v; for (int a : mi[i]) { dfs2(a, v); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for (int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; adj[a-1].push_back(b-1); adj[b-1].push_back(a-1); } for (int i = 0; i < n; i++) { cin >> mag[i]; } dfs(0, -1); if (minM == 1){ for (int i = 0; i < n; i++){ if (path[i] == maxP){ dfs2(i, i+1); } } bool twok = false; for (int i = 0; i < n; i++){ if (mag[i] == 2){ int count = 0; for (int a : adj[i]){ if (pn[a] != 0){ count++; if (count >= 2){ twok = true; break; } } } } } if (twok){ cout << "2/" << (2*maxP+1); } else { cout << "1/" << maxP; } } else { cout << minM << "/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...