제출 #512378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
512378		kartel	Magenta (COCI21_magenta)	C++14	30 / 110	25 ms	3668 KiB

Main

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

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50