Submission #988228

#	Time	Username	Problem	Language	Result	Execution time	Memory
988228		HasanV11010238	Magenta (COCI21_magenta)	C++17	30 / 110	199 ms	16348 KiB

Main

#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
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50