Submission #512380

#	Time	Username	Problem	Language	Result	Execution time	Memory
512380		kartel	Magenta (COCI21_magenta)	C++14	110 / 110	142 ms	11928 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;

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(int a, int b) {
    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
*/

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