Submission #512379

#TimeUsernameProblemLanguageResultExecution timeMemory
512379kartelMagenta (COCI21_magenta)C++14
Compilation error
0 ms0 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; const int Ns = 105; int n; vector <pair <int, int> > g[N]; bool is_end[N]; bool can[N]; vector <pair <int, int> > gr[Ns][Ns][2]; int cnt[Ns][Ns][2]; bool win[Ns][Ns][2], lose[Ns][Ns][2]; 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); } } } void brute() { for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { for (int par = 0; par < 2; par++) { if (par) { for (auto to : g[b]) { int u = to.F, color = to.S; if (color != blue) { gr[a][u][par ^ 1].pb({a, b}); cnt[a][b][par]++; } } } else { for (auto to : g[a]) { int u = to.F, color = to.S; if (color != red) { gr[u][b][par ^ 1].pb({a, b}); cnt[a][b][par]++; } } } } } } queue <pair <pair <int, int>, int> > q; for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { for (int par = 0; par < 2; par++) { if (a == b) { win[a][b][par] = 1; q.push({{a, b}, par}); } else { if (!cnt[a][b][par]) { q.push({{a, b}, par}); lose[a][b][par] = 1; } } } } } while (sz(q)) { int a = q.front().F.F, b = q.front().F.S, par = q.front().S; q.pop(); if (lose[a][b][par]) { for (auto p : gr[a][b][par]) { int na = p.F; int nb = p.S, npar = par ^ 1; if (!win[na][nb][npar]) { q.push({{na, nb}, npar}); win[na][nb][npar] = 1; } } } else { for (auto p : gr[a][b][par]) { int na = p.F; int nb = p.S, npar = par ^ 1; cnt[na][nb][npar]--; if (!cnt[na][nb][npar]) { q.push({{na, nb}, npar}); lose[na][nb][npar] = 1; } } } } cout << (win[a][b][0] ? "Paula" : (lose[a][b][0] ? "Marin" : "Magenta")); exit(0); } 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}); } } } if (n <= 100) { brute(a, b); } vector <int> da(n + 1); vector <int> db(n + 1); bfs(a, red, da); bfs(b, blue, db); bool bada = 1; for (auto to : g[a]) { int i = to.F; bada &= (da[i] == 1e9 || da[i] > db[i]); } if (bada) { cout << "Marin"; return 0; } bool badb = 1; for (auto to : g[b]) { int i = to.F; 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) queue <int> q; q.push(b); while (sz(q)) { int v = q.front(); q.pop(); can[v] = 1; for (auto to : g[v]) { int u = to.F; if (db[u] == 1e9) { continue; } if (db[u] == db[v] + 1 && db[u] < da[u]) { q.push(u); } } } for (int i = 1; i <= n; i++) { if (!can[i]) { continue; } int cnt_good = 0; for (auto to : g[i]) { int u = to.F; int clr = to.S; if (!can[u]) { continue; } 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++) { if (!can[i]) { continue; } bool have = 0; for (auto to : g[i]) { if (!can[to.F]) { continue; } 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; if (!can[i]) { continue; } for (auto to : g[i]) { int u = to.F; if (!can[u]) { continue; } if (db[u] < da[u] && db[u] + 1 == db[i]) { have = 1; } } for (auto to : g[i]) { int u = to.F; if (!can[u]) { continue; } 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; queue <int> q; q.push(a); while (sz(q)) { int v = q.front(); q.pop(); can[v] = 1; for (auto to : g[v]) { int u = to.F; if (da[u] == 1e9) { continue; } if (da[u] == da[v] + 1 && da[u] <= db[u]) { q.push(u); } } } /// 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++) { if (!can[i]) { continue; } int cnt_good = 0; for (auto to : g[i]) { int u = to.F; int clr = to.S; if (!can[u]) { continue; } 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; if (!can[i]) { continue; } for (auto to : g[i]) { if (!can[to.F]) { continue; } 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; if (!can[i]) { continue; } for (auto to : g[i]) { int u = to.F; if (!can[u]) { continue; } 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 (!can[u]) { continue; } 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 plava 7 8 magenta 7 9 magenta 8 10 magenta 9 11 magenta 9 12 magenta */

Compilation message (stderr)

Main.cpp: In function 'void brute()':
Main.cpp:107:18: error: 'a' was not declared in this scope
  107 |     cout << (win[a][b][0] ? "Paula" : (lose[a][b][0] ? "Marin" : "Magenta"));
      |                  ^
Main.cpp:107:21: error: 'b' was not declared in this scope
  107 |     cout << (win[a][b][0] ? "Paula" : (lose[a][b][0] ? "Marin" : "Magenta"));
      |                     ^
Main.cpp: In function 'int main()':
Main.cpp:133:19: error: too many arguments to function 'void brute()'
  133 |         brute(a, b);
      |                   ^
Main.cpp:44:6: note: declared here
   44 | void brute() {
      |      ^~~~~