oj.uz

Submission #853856

# Submission time Handle Problem Language Result Execution time Memory
853856 2023-09-25T10:20:47 Z noyancanturk Magenta (COCI21_magenta) C++17
30 / 110
 40 ms 10108 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);
    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.second!=a&&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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4600 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4696 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 10076 KB Output is correct
2 Correct 32 ms 9980 KB Output is correct
3 Correct 34 ms 10108 KB Output is correct
4 Correct 33 ms 10068 KB Output is correct
5 Correct 33 ms 10076 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Incorrect 1 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4600 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4696 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 40 ms 10076 KB Output is correct
15 Correct 32 ms 9980 KB Output is correct
16 Correct 34 ms 10108 KB Output is correct
17 Correct 33 ms 10068 KB Output is correct
18 Correct 33 ms 10076 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Incorrect 1 ms 4444 KB Output isn't correct
21 Halted 0 ms 0 KB -