Submission #366339

#	Time	Username	Problem	Language	Result	Execution time	Memory
366339		ajpiano	Magenta (COCI21_magenta)	C++17	30 / 110	94 ms	7628 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

typedef long long ll;
typedef pair<int,int> pi;

const int large = 1e5+1;
const int inf = 1e9;
vector<pi> edges[large];

//Marin safe or Paula safe
bool ms = 0, ps = 0;

vector<int> distm, distp, d;

void df(int node, int par, int dist, vector<int> &cur, int bad){
    cur[node] = dist;
    for(auto &a: edges[node]){
        if(a.f == par) continue;
        if(a.s == bad) continue;
        df(a.f,node,dist+1,cur,bad);
    }

}
//inf node, found ans
bool draw(int node, int par, vector<int> &d1, vector<int> &d2, int add){
    bool found = 0;
    bool ans = 0;
    for(auto &a: edges[node]){
        if(a.f == par) continue;
        if(d1[a.f] == inf) continue;
        if(d1[a.f] >= d2[a.f]+add) continue;
        ans |= draw(a.f,node,d1,d2,add);
        found |= (d2[a.f] == inf);
    }
    if(d2[node] == inf && found == 1) ans = 1;
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    distm.resize(n+1, inf); distp.resize(n+1, inf); d.resize(n+1, inf);
    int a, b; cin >> a >> b;
    for(int i = 0; i < n-1; i++){
        int x,y; cin >> x >> y;
        string c; int col; cin >> c;
        if(c == "plava") col = 0;
        else if(c == "crvena") col = 1;
        else col = 2;
        edges[x].push_back({y,col});
        edges[y].push_back({x,col});
    }
    //check alone
    bool good = 0;
    for(auto &e: edges[a]){
        if(e.s != 1 && e.f != b){
            good = 1; break;
        }
    }
    if(!good){
        cout << "Marin\n"; return 0;
    }
    good = 0;
    for(auto &e: edges[b]){
        if(e.s != 0 && e.f != a){
            good = 1; break;
        }
    }
    if(!good){
        cout << "Paula\n"; return 0;
    }
    //fill out distances
    df(a,0,0,distp,1);
    df(b,0,0,distm,0);
    df(a,0,0,d,5);
    //check odd or even
    if(d[b]&1) ms = 1;
    else ps = 1;
    //check if draw
    if(ps == 0){
        bool ans = draw(a,0,distp,distm,1);
        if(ans == 0) cout << "Marin\n";
        else cout << "Magenta\n";
    }
    else if(ms == 0){
        bool ans = draw(b,0,distm,distp,0);
        if(ans == 0) cout << "Paula\n";
        else cout << "Magenta\n";
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50