oj.uz

Submission #988263

# Submission time Handle Problem Language Result Execution time Memory
988263 2024-05-24T11:31:27 Z HasanV11010238 Magenta (COCI21_magenta) C++17
30 / 110
 323 ms 16588 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, difr = 0;
void dfs(int x, int p, int depth){
    if (x == sp2){
        difr = depth;
    }
    for (auto el : ve[x]){
        if (el[0] != p){
            dfs(el[0], x, depth + 1);
        }
    }
}
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)){
            if (dist2[el[0]] == INF) 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)){
            if (dist1[el[0]] == INF) 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);
    dfs(sp1, sp1, 0);
    if (difr % 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 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 16212 KB Output is correct
2 Correct 174 ms 16228 KB Output is correct
3 Correct 323 ms 16588 KB Output is correct
4 Correct 205 ms 16344 KB Output is correct
5 Correct 228 ms 16216 KB Output is correct
6 Correct 1 ms 548 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 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -