제출 #1276406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276406		warrenn	Magenta (COCI21_magenta)	C++20	110 / 110	96 ms	9432 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];
int leng=0; int a,b;

void dfs(int cur,int c,int par){
    for(auto x : adj[cur]){
        if(x.first==par)continue;
        if(x.first==b)leng=dist[cur][c]+1;
        if(x.second==1-c)continue;
        dist[x.first][c]=dist[cur][c]+1;
        dfs(x.first,c,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;
        
        if(dist[x.first][siapa]==-1 && dist[cur][siapa]==-1){
            oke=true;
        }
        solve(x.first,cur);
    }
}

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

    int n;
    cin>>n;
    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[0]=='p'){
            col=0;
        }
        else if(s[0]=='c'){
            col=1;
        }
        else{
            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,0,-1);
    dfs(b,1,-1);
    
    
    if(leng%2==1){
        siapa=1;
    }
    else{
        siapa=0;
    }
    
    if(siapa==0){
        solve(b,-1);
        if(oke){
            cout<<"Magenta"<<endl;
        }
        else{
            cout<<"Paula"<<endl;
        }
    }
    else{
        solve(a,-1);
        if(oke){
            cout<<"Magenta"<<endl;
        }
        else{
            cout<<"Marin"<<endl;
        }
    }
}

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