Submission #541363

#	Time	Username	Problem	Language	Result	Execution time	Memory
541363		AlperenT	Magenta (COCI21_magenta)	C++17	110 / 110	70 ms	8956 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, INF = 1e9 + 5;

int n, a, b, x, y, adist[N], bdist[N];

string str;

char c;

vector<pair<int, char>> tree[N];

bool isainf, isbinf;

void dfsa(int v, int p, int d){
    adist[v] = d;

    for(auto e : tree[v]){
        if(e.first != p && e.second != 'R'){
            dfsa(e.first, v, d + 1);
        }
    }
}

void dfsb(int v, int p, int d){
    bdist[v] = d;

    for(auto e : tree[v]){
        if(e.first != p && e.second != 'B'){
            dfsb(e.first, v, d + 1);
        }
    }
}

void checka(int v, int p, int d){
    for(auto e : tree[v]){
        if(e.first != p && e.second != 'R'){
            if(bdist[e.first] > d - 1 || bdist[e.first] % 2 != (d - 1) % 2){
                checka(e.first, v, d + 1);

                if((((bdist[v] % 2 != ((d + 1) - 1) % 2) || bdist[v] == INF) && ((bdist[e.first] % 2 != (d - 1) % 2) || bdist[e.first] == INF))) isainf = true;
            }
        }
    }
}

void checkb(int v, int p, int d){
    for(auto e : tree[v]){
        if(e.first != p && e.second != 'B'){
            if(adist[e.first] > d || adist[e.first] % 2 != d % 2){
                checkb(e.first, v, d + 1);

                if(((adist[v] % 2 != (d + 1) % 2 || adist[v] == INF) && (adist[e.first] % 2 != d % 2 || adist[e.first] == INF))) isbinf = true;
            }
        }
    }
}

int dist(int v, int p, int d){
    if(v == b) return d;
    else{
        int mx = -1;

        for(auto e : tree[v]){
            if(e.first != p){
                mx = max(mx, dist(e.first, v, d + 1));
            }
        }

        return mx;
    }
}

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

    cin >> n;

    cin >> a >> b;

    for(int i = 1; i <= n - 1; i++){
        cin >> x >> y >> str;

        if(str == "plava") c = 'B';
        else if(str == "crvena") c = 'R';
        else if(str == "magenta") c = 'M';

        tree[x].push_back({y, c});
        tree[y].push_back({x, c});
    }

    fill(adist, adist + N, INF), fill(bdist, bdist + N, INF);

    dfsa(a, 0, 0), dfsb(b, 0, 0);

    checka(a, 0, 1), checkb(b, 0, 1);

    if(isainf && isbinf) cout << "Magenta";
    else if(isainf) cout << "Paula";
    else if(isbinf) cout << "Marin";
    else{
        int ans = dist(a, 0, 0);

        if(adist[b] == INF && bdist[a] == INF) cout << "Marin";
        else if(ans == -1) cout << "Marin";
        else if(ans % 2 == 0) cout << "Paula";
        else cout << "Marin";
    }
}

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