oj.uz

Submission #512374

# Submission time Handle Problem Language Result Execution time Memory
512374 2022-01-16T10:07:04 Z kartel Magenta (COCI21_magenta) C++14
0 / 110
 24 ms 3632 KB 
#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;
typedef long long ll;

const int N = 105;

vector <pair <int, int> > gr[N][N][2];
int cnt[N][N][2];
vector <pair <int, int> > g[N];
int a, b, n;
bool win[N][N][2], lose[N][N][2];

int main() {
    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});
            }
        }
    }

    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});
                }
            }
        }
    }
    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"));
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 0 ms 716 KB Output is correct
3 Correct 1 ms 800 KB Output is correct
4 Incorrect 1 ms 716 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 3632 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 0 ms 716 KB Output is correct
3 Correct 1 ms 800 KB Output is correct
4 Incorrect 1 ms 716 KB Output isn't correct
5 Halted 0 ms 0 KB -