제출 #512285

#제출 시각아이디문제언어결과실행 시간메모리
512285kartelMagenta (COCI21_magenta)C++14
30 / 110
135 ms9668 KiB
#include <bits/stdc++.h> #define blue 0 #define red 1 #define purple 2 #define pb push_back #define F first #define S second #define sz(x) (int)x.size() using namespace std; const int N = 2e5 + 500; int n; vector <pair <int, int> > g[N]; bool is_end[N]; void bfs(int start, int bad_color, vector <int> &d) { for (int i = 1; i <= n; i++) { d[i] = 1e9; } queue <int> q; q.push(start); d[start] = 0; while (sz(q)) { int v = q.front(); q.pop(); for (auto to : g[v]) { int u = to.F; int clr = to.S; if (clr == bad_color || d[u] != 1e9) { continue; } d[u] = d[v] + 1; q.push(u); } } } int main() { int a, b; cin >> n; cin >> a >> b; for (int i = 1; i < n; i++) { int u, v; string c; cin >> u >> v >> c; if (c == "plava") { g[u].pb({v, blue}); g[v].pb({u, blue}); } else { if (c == "crvena") { g[u].pb({v, red}); g[v].pb({u, red}); } else { g[u].pb({v, purple}); g[v].pb({u, purple}); } } } vector <int> da(n + 1); vector <int> db(n + 1); bfs(a, red, da); bfs(b, blue, db); bool bada = 1; for (int i = 1; i <= n; i++) { if (i == a) { continue; } bada &= (da[i] == 1e9 || da[i] > db[i]); } if (bada) { cout << "Marin"; return 0; } bool badb = 1; for (int i = 1; i <= n; i++) { if (i == b) { continue; } badb &= (db[i] == 1e9); } if (badb) { cout << "Paula"; return 0; } if (da[b] != 1e9 && (da[b] % 2 == 0 || db[a] == 1e9)) { /// first player go to the second bool both = 0; /// mark all vertices v, in that the second player can stay always(v -> u, u -> v, where u is adjacent of v) for (int i = 1; i <= n; i++) { int cnt_good = 0; for (auto to : g[i]) { int u = to.F; int clr = to.S; cnt_good += (clr != blue); } is_end[i] = (cnt_good == 1); } /// Can we have some vertice v, in that we can jump (u -> v, v -> u) and the first player can't stop him in the vertice v for (int i = 1; i <= n; i++) { bool have = 0; for (auto to : g[i]) { have |= (is_end[to.F] && (da[to.F] == 1e9 || da[to.F] > db[to.F])); } if (have && da[i] > db[i] && (da[i] - db[i]) % 2 != 0) { both = 1; } } /// Can we run from the component of the first player? for (int i = 1; i <= n; i++) { bool have = 0; for (auto to : g[i]) { int u = to.F; if (db[u] < da[u] && db[u] + 1 == db[i]) { have = 1; } } for (auto to : g[i]) { int u = to.F; if (have && da[i] == 1e9 && da[u] == 1e9 && db[i] + 1 == db[u]) { both = 1; } } } if (both) { cout << "Magenta"; } else { cout << "Paula"; } return 0; } if (db[a] != 1e9 && (db[a] % 2 || da[b] == 1e9)) { /// second player go to the first bool both = 0; /// mark all vertices v, in that the first player can stay always(v -> u, u -> v, where u is adjacent of v) for (int i = 1; i <= n; i++) { int cnt_good = 0; for (auto to : g[i]) { int u = to.F; int clr = to.S; cnt_good += (clr != red); } is_end[i] = (cnt_good == 1); } /// Can we have some vertice v, in that we can jump (u -> v, v -> u) and the second player can't stop him in the vertice v for (int i = 1; i <= n; i++) { bool have = 0; for (auto to : g[i]) { have |= (is_end[to.F] && (db[to.F] >= da[to.F] || db[to.F] == 1e9) && da[to.F] != 1e9); } if (have && db[i] >= da[i] && (db[i] - da[i]) % 2 == 0 && da[i] != 1e9) { both = 1; } } /// Can we run from the component of the second player? for (int i = 1; i <= n; i++) { bool have = 0; for (auto to : g[i]) { int u = to.F; if (da[u] <= db[u] && db[u] != 1e9 && da[u] + 1 == da[i]) { have = 1; } } for (auto to : g[i]) { int u = to.F; if (have && db[i] == 1e9 && db[u] == 1e9 && da[i] + 1 == da[u]) { both = 1; } } } if (both) { cout << "Magenta"; } else { cout << "Marin"; } return 0; } cout << "Magenta"; } /* 5 3 5 4 2 crvena 3 5 plava 1 5 magenta 4 1 magenta 5 2 1 1 2 magenta 2 3 magenta 3 4 magenta 3 5 magenta 12 6 9 1 2 magenta 2 3 magenta 3 4 magenta 3 5 magenta 2 6 magenta 1 7 crvena 7 8 magenta 7 9 magenta 8 10 magenta 9 11 magenta 9 12 magenta */

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:94:21: warning: unused variable 'u' [-Wunused-variable]
   94 |                 int u = to.F;
      |                     ^
Main.cpp:143:21: warning: unused variable 'u' [-Wunused-variable]
  143 |                 int u = to.F;
      |                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...