oj.uz

Submission #541359

# Submission time Handle Problem Language Result Execution time Memory
541359 2022-03-23T08:39:32 Z AlperenT Magenta (COCI21_magenta) C++17
30 / 110
 88 ms 7184 KB 
#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) 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) 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 3 ms 3456 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Incorrect 2 ms 3412 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 7172 KB Output is correct
2 Correct 52 ms 7084 KB Output is correct
3 Correct 88 ms 7064 KB Output is correct
4 Correct 69 ms 7184 KB Output is correct
5 Correct 71 ms 7096 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 3 ms 3456 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Incorrect 2 ms 3412 KB Output isn't correct
7 Halted 0 ms 0 KB -