제출 #853857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853857		noyancanturk	Magenta (COCI21_magenta)	C++17	110 / 110	49 ms	11856 KiB

Main

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define lim 100000
using namespace std;
const int mod=1000000007ll;

vector<pair<char,int>>e[lim];
int depth1[lim],depth2[lim];
bool can1[lim],can2[lim];
bool safe1[lim],safe2[lim];

void can_bfs(int i,char can,int*depth,bool*cany){
    depth[i]=0;
    cany[i]=1;
    queue<pair<int,int>>q;
    for(auto j:e[i]){
        q.push({j.second,i});
        cany[j.second]=(j.first==can||j.first=='m');
        depth[j.second]=1;
    }
    while(q.size()){
        auto cur=q.front();
        q.pop();
        for(auto j:e[cur.first]){
            if(j.second!=cur.second&&depth[j.second]==-1){
                q.push({j.second,cur.first});
                depth[j.second]=depth[cur.first]+1;
                cany[j.second]=(cany[cur.first]&&(j.first==can||j.first=='m'));
            }
        }
    }
}

void solve(){
    int n;
    cin>>n;
    int a,b;
    cin>>a>>b;
    a--,b--;
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        x--,y--;
        string s;
        cin>>s;
        e[x].pb({s[0],y});
        e[y].pb({s[0],x});
        //cerr<<"ok "<<i<<"\n";
    }
    //cerr<<"hmm\n";
    memset(depth1,-1,sizeof(depth1));
    memset(depth2,-1,sizeof(depth2));
    can_bfs(a,'p',depth1,can1);
    can_bfs(b,'c',depth2,can2);
    int wow1=0,wow2=0;
    for(auto j:e[a]){
        if(j.second!=b&&j.first!='c'){
            wow1=1;
            break;
        }
    }
    for(auto j:e[b]){
        if(j.first!='p'){
            wow2=1;
            break;
        }
    }
    if(!wow1){
        cout<<"Marin\n";
        return;
    }else if(!wow2){
        cout<<"Paula\n";
        return;
    }
    for(int i=0;i<n;i++){
        //cerr<<can2[i]<<"\n";
        safe1[i]=0;
        safe2[i]=0;
        for(auto j:e[i]){
            if(can1[i]&&can1[j.second]&&!can2[i]&&!can2[j.second]){
                safe1[i]=1;
            }
            if(can2[i]&&can2[j.second]&&!can1[i]&&!can1[j.second]){
                safe2[i]=1;
            }
        }
        //cerr<<safe1[i]<<" "<<safe2[i]<<" safety\n";
    }
    bool end1=0,end2=0;
    for(int i=0;i<n;i++){
        if(safe1[i]&&depth1[i]<=depth2[i]){
            //cerr<<"first can "<<i<<"\n";
            end1=1;
        }
        if(safe2[i]&&depth2[i]<depth1[i]){
            //cerr<<"second can "<<i<<"\n";
            end2=1;
        }
    }
    //cerr<<end1<<" "<<end2<<" result\n";
    //cerr<<depth1[b]<<"\n";
    bool winner=(depth1[b]%2);
    //cerr<<winner<<"\n";
    if(!winner&&!end2){
        cout<<"Paula\n";
        return;
    }
    if(winner&&!end1){
        cout<<"Marin\n";
        return;
    }
    cout<<"Magenta\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

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