Submission #512324

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

int n;
vector <pair <int, int> > g[N];
bool is_end[N];
bool can[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 (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)
        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);
        }
        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);
                }
            }
        }

        /// 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]) {
                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 crvena
7 8 magenta
7 9 magenta
8 10 magenta
9 11 magenta
9 12 magenta
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:91:21: warning: unused variable 'u' [-Wunused-variable]
   91 |                 int u = to.F;
      |                     ^

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