oj.uz

Submission #853791

# Submission time Handle Problem Language Result Execution time Memory
853791 2023-09-25T08:59:10 Z noyancanturk Magenta (COCI21_magenta) C++17
30 / 110
 36 ms 11896 KB 
#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);
    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";
    if(end1&&end2){
        cout<<"Magenta\n";
        return;
    }
    //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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Incorrect 1 ms 4440 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 35 ms 11856 KB Output is correct
2 Correct 36 ms 11856 KB Output is correct
3 Correct 36 ms 11856 KB Output is correct
4 Correct 34 ms 11856 KB Output is correct
5 Correct 34 ms 11896 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Incorrect 1 ms 4440 KB Output isn't correct
5 Halted 0 ms 0 KB -