oj.uz

Submission #988228

# Submission time Handle Problem Language Result Execution time Memory
988228 2024-05-24T10:28:21 Z HasanV11010238 Magenta (COCI21_magenta) C++17
30 / 110
 199 ms 16348 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000
map<string, int> cols;
int n, sp1, sp2, a, b;
vector<vector<vector<int>>> ve;
vector<int> dist1, dist2;
bool esc1 = 0, esc2 = 0;
int comp1 = 0, comp2 = 0;
void dfs1(int x, int p, int depth){
    comp1++;
    dist1[x] = depth;
    for (auto el : ve[x]){
        if (el[0] != p && (el[1] == 1 || el[1] == 3)){
            dfs1(el[0], x, depth + 1);
        }
    }
}
void dfs2(int x, int p, int depth){
    comp2++;
    dist2[x] = depth;
    for (auto el : ve[x]){
        if (el[0] != p && (el[1] == 2 || el[1] == 3)){
            dfs2(el[0], x, depth + 1);
        }
    }
}
void escape1(int x, int p){
    if (dist1[x] > dist2[x]){
        return;
    }
    int sa = 0;
    for (auto el : ve[x]){
        if (el[0] != p && (el[1] == 1 || el[1] == 3)){
            sa++;
            escape1(el[0], x);
        }
    }
    if (sa > 0 && dist2[x] == INF){
        esc1= 1;
    }
}
void escape2(int x, int p){
    if (dist1[x] <= dist2[x]){
        return;
    }
    int sa = 0;
    for (auto el : ve[x]){
        if (el[0] != p && (el[1] == 2 || el[1] == 3)){
            sa++;
            escape2(el[0], x);
        }
    }
    if (sa > 0 && dist1[x] == INF){
        esc2 = 1;
    }
}
int main(){
    string col;
    cols["plava"] = 1;
    cols["crvena"] = 2;
    cols["magenta"] = 3;
    cin>>n>>sp1>>sp2;
    sp1--, sp2--;
    dist1.assign(n, INF), dist2.assign(n, INF);
    ve.resize(n);
    for (int i = 0; i < n - 1; i++){
        cin>>a>>b>>col;
        a--, b--;
        ve[a].push_back({b, cols[col]});
        ve[b].push_back({a, cols[col]});
    }
    dfs1(sp1, sp1, 0);
    dfs2(sp2, sp2, 0);
    escape1(sp1, sp1);
    escape2(sp2, sp2);
    int val;
    if (dist1[sp2] != INF){
        val = dist1[sp2];
    }
    else if (dist2[sp1] != INF){
        val = dist2[sp1];
    }
    else{
        if (comp1 == 1){
            cout<<"Marin";
        }
        else if (comp2 == 2){
            cout<<"Paula";
        }
        else{
            cout<<"Magenta";
        }
        return 0;
    }
    if (val % 2 == 1){
        if (esc1 == 1){
            cout<<"Magenta";
        }
        else{
            cout<<"Marin";
        }
    }
    else{
        if (esc2 == 1){
            cout<<"Magenta";
        }
        else{
            cout<<"Paula";
        }
    }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 16288 KB Output is correct
2 Correct 177 ms 16208 KB Output is correct
3 Correct 155 ms 16348 KB Output is correct
4 Correct 146 ms 16208 KB Output is correct
5 Correct 150 ms 16208 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -