Submission #588346

#TimeUsernameProblemLanguageResultExecution timeMemory
588346MilosMilutinovicMagenta (COCI21_magenta)C++14
30 / 110
85 ms8868 KiB
/** * author: wxhtzdy * created: 02.07.2022 21:03:17 **/ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; int a, b; cin >> a >> b; --a; --b; vector<vector<pair<int, int>>> g(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; string foo; cin >> foo; --u; --v; int t; if (foo == "plava") { t = 1; } else if (foo == "magenta") { t = 2; } else { t = 3; } g[u].emplace_back(v, t); g[v].emplace_back(u, t); } vector<int> dep(n); vector<int> par(n); function<void(int, int)> Dfs = [&](int v, int pr) { par[v] = pr; dep[v] = dep[pr] + 1; for (auto& e : g[v]) { int u = e.first; if (u == pr) { continue; } Dfs(u, v); } }; Dfs(0, 0); int x = a, y = b, dis = 0; while (x != y) { if (dep[x] > dep[y]) { x = par[x]; } else { y = par[y]; } dis += 1; } vector<vector<int>> dist(2, vector<int>(n, -1)); { dist[0][a] = 0; vector<int> que(1, a); for (int x = 0; x < (int) que.size(); x++) { int i = que[x]; for (auto& e : g[i]) { int u = e.first; int w = e.second; if (w <= 2 && dist[0][u] == -1) { dist[0][u] = dist[0][i] + 1; que.push_back(u); } } } } { dist[1][b] = 0; vector<int> que(1, b); for (int x = 0; x < (int) que.size(); x++) { int i = que[x]; for (auto& e : g[i]) { int u = e.first; int w = e.second; if (w >= 2 && dist[1][u] == -1) { dist[1][u] = dist[1][i] + 1; que.push_back(u); } } } } bool have = false; for (auto& e : g[a]) { if (e.first != b && e.second <= 2) { have = true; } } if (!have) { cout << "Marin" << '\n'; return 0; } if (dis % 2 == 0) { if (dist[0][b] == -1) { cout << "Magenta" << '\n'; return 0; } bool ok = false; function<void(int, int)> Dfs = [&](int v, int pr) { for (auto& e : g[v]) { int u = e.first; int w = e.second; if (u == pr || w == 1 || (dist[0][u] != -1 && dist[0][u] <= dist[1][u])) { continue; } if (w == 3) { ok = true; } Dfs(u, v); } }; Dfs(b, b); cout << (ok ? "Magenta" : "Paula") << '\n'; } else { if (dist[1][a] == -1) { cout << "Magenta" << '\n'; return 0; } bool ok = false; function<void(int, int)> Dfs = [&](int v, int pr) { for (auto& e : g[v]) { int u = e.first; int w = e.second; if (u == pr || w == 3 || (dist[1][u] != -1 && dist[1][u] < dist[0][u])) { continue; } if (w == 1) { ok = true; } Dfs(u, v); } }; Dfs(a, a); cout << (ok ? "Magenta" : "Marin") << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...