Submission #1136932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136932		monaxia	Magenta (COCI21_magenta)	C++20	110 / 110	35 ms	8192 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define mod (long long)(1e9 + 7)
#define eps (long long)(1e-9)
#define vektor vector
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
 
const ull Mod = 1e9 + 7;
const ll LIMIT = 2e5;

int n, W, L, cnt_fr = 1, cnt_sc = 1;

struct edge{
    int v, color;
};

int distance(int node, int target, vector <vector <edge>> &graph){
    vector <int> v(n + 1, 0);
    queue <pair <int, int>> q;

    q.push({node, 0});
    v[node] = 1;

    while(!q.empty()){
        int u = q.front().fr, dist = q.front().sc;
        q.pop();

        for(auto& x : graph[u]){
            if(v[x.v]) continue;
            v[x.v] = 1; 

            if(x.v == target) return dist + 1;

            q.push({x.v, dist + 1});
        }
    }
}

void bfs_able(int node, int color, vector <vector <edge>>& graph, vector <int>& visit){
    queue <int> q;
    q.push(node);
    visit[node] = 1;

    while(!q.empty()){
        int u = q.front();
        q.pop();

        for(auto& x : graph[u]){
            int v = x.v, c = x.color;
            if(visit[v]) continue;
            if(c == color || c == 0){
                visit[v] = 1;
                q.push(v);
            }
            
        }
    }
}

void bfs_init(int first, int second, int phd, vector <vector <edge>>& graph, vector <int>& visit){
    queue <pair <int, int>> qfr, qsc;
    qfr.push({first, 1});
    qsc.push({second, 1});

    // loser will mark 1 when visited, winners will mark number 2 when visited and override 1 if can

    int valf = 1, vals = 2, gen = 0;
    if(phd) swap(valf, vals);

    int phd1 = 0, phd2 = 0;

    visit[first] = valf;
    visit[second] = vals;

    while(!qfr.empty() || !qsc.empty()){
        gen ++;

        int u;
        while(!qfr.empty() && qfr.front().sc == gen){
            u = qfr.front().fr;
            qfr.pop();


            for(auto& x : graph[u]){
                int v = x.v, c = x.color;

                if(c > 1) continue;
                if(visit[v]) continue;

                cnt_fr ++;
                visit[v] = valf;
                qfr.push({v, gen + 1});
            }
        }

        phd2 ++;
        while(!qsc.empty() && qsc.front().sc == gen){
            u = qsc.front().fr;
            qsc.pop();


            for(auto& x : graph[u]){
                int v = x.v, c = x.color;

                if(c == 1) continue;
                if(visit[v]) continue;

                cnt_sc ++;
                visit[v] = vals;
                qsc.push({v, gen + 1});
            }
        }
    }
}

bool check(int node, vector <vector <edge>>& graph, vector <int>& loser, vector <int>& winner, vector <int>& total){
    vector <int> visit(n + 1, 0);
    queue <pair <int, int>> q;
    q.push({node, 0});
    visit[node] = 1;

    while(!q.empty()){
        int u = q.front().fr, cnt = q.front().sc;
        q.pop();

        if(cnt >= 2) {
            return 1;
        }

        for(auto& x : graph[u]){
            int v = x.v;

            if(visit[v]) continue;
            visit[v] = 1;   

            if(loser[v] == 1 && total[v] == 1 && !winner[v]) q.push({v, cnt + 1});
            else q.push({v, 0});
        }
    }

    return 0;
}

int edges(int first, int second, vector <vector <edge>>& graph){
    vector <int> visit(n + 1, 0);

    visit[second] = 1;

    bool moveable = 0;

    for(auto& x : graph[first]){
        int v = x.v, c = x.color;
        if(c <= 1 && !visit[v]){
            moveable = 1;
            break;
        }
    }

    if(!moveable) return 2;

    moveable = 0;

    for(auto& x : graph[second]){
        int v = x.v, c = x.color;
        if(c != 1){
            moveable = 1;
            break;
        }
    }

    if(!moveable) return 1;

    return 0;
}

void solve(){
    cin >> n >> W >> L;

    vector <vector <edge>> graph(n + 1);
    vector <int> able_fr(n + 1, 0), able_sc(n + 1, 0);

    for(int i = 1; i < n; i ++){
        int u, v, color;
        string c;
        cin >> u >> v >> c;

        if(c == "magenta") color = 0;
        else if(c == "plava") color = 1;
        else color = 2;

        graph[u].pb({v, color});
        graph[v].pb({u, color});
    } 

    int edgecase = edges(W, L, graph);

    if(edgecase){
        // cout << "!!";
        if(edgecase == 1) cout << "Paula";
        else cout << "Marin";
        return;
    }

    bfs_able(W, 1, graph, able_fr);
    bfs_able(L, 2, graph, able_sc);

    int phd = 1;

    if(distance(W, L, graph) & 1) phd = 0;

    vector <int> v(n + 1, 0);

    bfs_init(W, L, phd, graph, v);

    int winner = W;
    if(!phd) winner = L;

    bool fff;
    if(phd) fff = check(L, graph, able_sc, able_fr, v);
    else fff = check(W, graph, able_fr, able_sc, v);

    // cout << phd << ":\n";

    // for(int i = 1; i <= n; i ++) cout << v[i] << " " << able_fr[i] << " " << able_sc[i] << "\n"; cout << "\n";

    if(fff) cout << "Magenta";

    else{
        if(phd == 1) cout << "Paula";
        else cout << "Marin";
    }
}

 
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
 
    // if(fopen("nameholder.inp", "r")){
    //     freopen("nameholder.inp", "r", stdin);
    //     freopen("nameholder.out", "w", stdout);
    // }
    
    // cout << 1; return 0;
 
    ll n = 1;
 
    // cin >> n;
 
    while(n) {
        solve();
        n --;
        cout << "\n";
    }
 
    // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}
 
//                                   ++++                                           
//                          ++++-::......:--:::-=+++                                
//                    ++++=:............---.....--:..:=++++++                       
//                    +++++++::......................::=+++++                       
//             @@               ++++++++++:+++++++++                                
//             @%                                  @*                               
//              %%@@                    *****#*@@                                   
//             %%%%%                  @##**##***%                                   
//           @@@@@@+-*#*@             #####%+*##*@                                  
//                  %#+@%%@@@         ##-%:::-#*###@@                               
//                 =====:*:::        ###-:==::=#*%*                                 
//                    -====:::::+@@%@@%@#*--=*#%%#@%@   @%@                         
//                        @=====%=-@%=:::.:+-::::+::::::::::::%-----%% @@@@@        
//                        @@%#*@++%===+::-================@%@@@@+++++++@@@%%%@#%###%
//               @#***#@@   @##=%@===+--:+==+===+%*##@%%%@@@@@@@@@@:=  @%@%%%@#%%   
//    -@      @*#@         #####%:::-====+:::==---**%#@ *%%%%@@@@@@-:               
//    -=-*%  #          #***--%%::::::::+=-+#-----=**@*#     #+**#@#                
//     ----=----#+****=----=*#@=::::::=#-----------***%*%                           
//      ------------%*****##=@==::::::+%-----------***%**                           
//       +-----------------*@++%::::::::-----------****@*#                          
//         =------------% @%=+%#+:::::::* #-----*--**** **                          
//            ----%--%    *==+++++=+=##*:%   ---=--**** **                          
//                       %@@@@@@@@@==@+%%%%@   ----**** *#                          
//                     @=*+%@@@%@@=++=:%:::%      #***@@#                           
//                    #+++++++++#==++-::::::     @**** *#                           
//                   =+++++++++++==+++:::::::   ####@ #%                            
//                  +++++++++++=@ @++++::::::@      @#                              
//                 @+++++++++=@    =*++=:::::@                                      
//                 ++++++++@       @++++:::::                                       
//                ++++++=           =++++:::                                        
//               =+++++@             =+++::::                                       
//             ++++++-@               =+++:+::                                      
//           @::+::::@                 =++::-:::                                    
//          +::=:::::                  @+*+:-+++-:                                  
//        @::+-:::::#                     +++::::::@                                
//       ::%=:::::::%@                    @%++::::***                               
//     @:+@*:::::::****@                   +@+++:-=*:*@                             
//    *:@@%::::::::=****                   @%@+++:::#**@                            
//   *%@@@-:::::::%=+==*@                   +@%+++:***+*                            
//  #%@@%%::::::::#+=-=#                    =+@+++++:::*+                           
// @####+::::::::%+=@#%#=@                  @**@@%=++::::@                          
// @   +:::::::::***#*@ @@###+=+=%@          +**#+=+*+:::-                          
//    =-:::::::%%%%@@          @#=*########%#+*%%+--@*+::%                          
//   +---%@                                   @@ =-:-**:#                           
//  %%%%%                                        @+--*@                             
// @%%%%@                                        @%%%%%                             
//                                                @%%@@

Compilation message (stderr)

Main.cpp: In function 'int distance(int, int, std::vector<std::vector<edge> >&)':
Main.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

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