제출 #1276400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276400		warrenn	Magenta (COCI21_magenta)	C++20	30 / 110	80 ms	9236 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long  

const int maxn=1e5;
int dist[maxn+2][2];
vector<pair<int,int> >adj[maxn+2];

void dfs(int cur,int par){
    for(auto x : adj[cur]){
        if(x.first==par || x.second==1)continue;
        dist[x.first][0]=dist[cur][0]+1;
        dfs(x.first,cur);
    }
}

void dfs2(int cur,int par){
    for(auto x : adj[cur]){
        // cout<<cur<<" "<<x.second<<endl;
        // cout<<x.first<<endl;
        if(x.first==par || x.second==0)continue;
       
        dist[x.first][1]=dist[cur][1]+1;
        dfs2(x.first,cur);
    }
}

int siapa=0;
bool oke=false;

void solve(int cur,int par){
    for(auto x : adj[cur]){
        if(x.first==par || (dist[x.first][siapa]!=-1 && dist[x.first][siapa]<=dist[x.first][1-siapa]))continue;
        if(x.second==siapa)continue;
    //    cout<<siapa<<" "<<cur<<endl;
        solve(x.first,cur);
        if(dist[x.first][siapa]==-1 && dist[cur][siapa]==-1){
            oke=true;
        }
    }
}

signed main(){
    memset(dist,-1,sizeof dist);

    int n;
    cin>>n;
    int a,b;
    cin>>a>>b;
    bool blue=false;
    bool red=false;

    for(int q=1;q<n;q++){
        int u,v;
        cin>>u>>v;
        string s;
        cin>>s;
        int col=0;
        if(s=="crvena"){
            col=1;
        }
        else if(s=="magenta"){
            col=2;
        }

        adj[u].push_back({v,col});
        adj[v].push_back({u,col});
        if(col!=0 && (u==b || v==b))red=true;
        if(col!=1 && ((u==a && v!=b)) || (u!=b && v==a))blue=true;
    }   
    if(blue==false){
        cout<<"Marin"<<endl;
        return 0;
    }
    if(red==false){
        cout<<"Paula"<<endl;
        return 0;
    }

    dist[a][0]=dist[b][1]=0;
    dfs(a,-1);
    dfs2(b,-1);
    
    
    if(dist[b][0]%2==1){
        siapa=1;
    }
    
    if(siapa==0){
        solve(a,-1);
        if(oke){
            cout<<"Magenta"<<endl;
        }
        else{
            cout<<"Paula"<<endl;
        }
    }
    else{
        solve(b,-1);
        if(oke){
            cout<<"Magenta"<<endl;
        }
        else{
            cout<<"Marin"<<endl;
        }
    }
}

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