Submission #386467

#	Time	Username	Problem	Language	Result	Execution time	Memory
386467		phathnv	Magenta (COCI21_magenta)	C++11	110 / 110	106 ms	10020 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e5 + 1;
const int INF = 1e9 + 7;

struct Edge{
    int u, v, c;
    Edge(int _u, int _v, int _c){
        u = _u;
        v = _v;
        c = _c;
    }
};

int n, a, b;
vector<Edge> adj[N];

int dist[N], distFromA[N], distFromB[N];
bool vst[N];

int dfs(int u, int p, int dist[], int type){
    if (p == -1)
        dist[u] = 0;
    int res = 1;
    for(Edge e : adj[u])
        if (e.v != p && (e.c & type)){
            dist[e.v] = dist[u] + 1;
            res += dfs(e.v, u, dist, type);
        }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> a >> b;
    for(int i = 1; i < n; i++){
        int u, v, c;
        string s;
        cin >> u >> v >> s;
        if (s == "plava")
            c = 1;
        else if (s == "crvena")
            c = 2;
        else
            c = 3;
        adj[u].push_back(Edge(u, v, c));
        adj[v].push_back(Edge(v, u, c));
    }

    for(int i = 1; i <= n; i++)
        dist[i] = distFromA[i] = distFromB[i] = INF;

    dfs(a, -1, dist, 3);
    dfs(a, -1, distFromA, 1);
    dfs(b, -1, distFromB, 2);
    bool ACanMove = 0, BCanMove = 0;
    for(Edge e : adj[a])
        if (e.v != b && (e.c & 1))
            ACanMove = 1;
    for(Edge e : adj[b])
        if ((e.c & 2))
            BCanMove = 1;

    if (!ACanMove){
        cout << "Marin";
        return 0;
    }
    if (!BCanMove){
        cout << "Paula";
        return 0;
    }

    if (dist[b] % 2 == 0){
        queue<int> qu;
        vst[b] = 1;
        qu.push(b);
        while(!qu.empty()){
            int u = qu.front();
            qu.pop();
            for(Edge e : adj[u]){
                int v = e.v;
                int c = e.c;
                if (distFromB[v] < distFromA[v] && !vst[v] && (c & 2)){
                    vst[v] = 1;
                    qu.push(v);
                }
            }
        }
        for(int i = 1; i <= n; i++)
            vst[i] &= (distFromA[i] == INF);
        for(int u = 1; u <= n; u++)
            for(Edge e : adj[u])
                if (vst[u] && vst[e.v]){
                    cout << "Magenta";
                    return 0;
                }
        cout << "Paula";
    } else {
        queue<int> qu;
        vst[a] = 1;
        qu.push(a);
        while(!qu.empty()){
            int u = qu.front();
            qu.pop();
            for(Edge e : adj[u]){
                int v = e.v;
                int c = e.c;
                if (distFromA[v] <= distFromB[v] && !vst[v] && (c & 1)){
                    vst[v] = 1;
                    qu.push(v);
                }
            }
        }
        for(int i = 1; i <= n; i++)
            vst[i] &= (distFromB[i] == INF);
        for(int u = 1; u <= n; u++)
            for(Edge e : adj[u])
                if (vst[u] && vst[e.v]){
                    cout << "Magenta";
                    return 0;
                }
        cout << "Marin";
    }
    return 0;
}

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