oj.uz

Submission #541358

# Submission time Handle Problem Language Result Execution time Memory
541358 2022-03-23T08:32:14 Z AlperenT Magenta (COCI21_magenta) C++17
30 / 110
 76 ms 9088 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 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 cout << "Marin";
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 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 63 ms 9036 KB Output is correct
2 Correct 57 ms 9028 KB Output is correct
3 Correct 76 ms 9088 KB Output is correct
4 Correct 72 ms 9084 KB Output is correct
5 Correct 63 ms 9036 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 3540 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 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 -