fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
  5. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  6. #define REP(i, a) for(int i = 0; i < (a); ++i)
  7. #define sz(a) (int)(a).size()
  8. #define all(a) (a).begin(), (a).end()
  9. #define bit(s, i) (((s) >> (i)) & 1)
  10. #define ii pair <int, int>
  11. #define fi first
  12. #define se second
  13. #define ll long long
  14. #define eb emplace_back
  15. #define pb push_back
  16. #define __builtin_popcount __builtin_popcountll
  17.  
  18. template <class X, class Y>
  19.     bool maxi(X &x, Y y) {
  20.         if(x < y) {
  21.             x = y;
  22.             return true;
  23.         }
  24.         return false;
  25.     }
  26.  
  27. template <class X, class Y>
  28.     bool mini(X &x, Y y) {
  29.         if(x > y) {
  30.             x = y;
  31.             return true;
  32.         }
  33.         return false;
  34.     }
  35.  
  36. const int N=1e5+5;
  37. const int INF=1e9;
  38.  
  39. int n,a,b,dA[N],dB[N],cntA,cntB;
  40. vector<ii> adj[N];
  41.  
  42. void bfsa(){
  43.     fill(dA+1,dA+1+n,INF);
  44.     queue<int>q;
  45.     dA[a]=0;
  46.     q.push(a);
  47.     while(q.size()){
  48.         int u=q.front();q.pop();
  49.         cntA+=u!=b;
  50.         for(auto [v,w]:adj[u]){
  51.             if(w==1) continue;
  52.             if(dA[v]>dA[u]+1){
  53.                 dA[v]=dA[u]+1;
  54.                 q.push(v);
  55.             }
  56.         }
  57.     }
  58. }
  59.  
  60. void bfsb(){
  61.     fill(dB+1,dB+1+n,INF);
  62.     queue<int>q;
  63.     dB[b]=0;
  64.     q.push(b);
  65.     while(q.size()){
  66.         ++cntB;
  67.         int u=q.front();q.pop();
  68.         for(auto [v,w]:adj[u]){
  69.             if(w==0) continue;
  70.             if(dB[v]>dB[u]+1){
  71.                 dB[v]=dB[u]+1;
  72.                 q.push(v);
  73.             }
  74.         }
  75.     }
  76. }
  77.  
  78. bool dfsa(int u, int p=-1){
  79.     if(dA[u]>dB[u]) return false;
  80.     for(auto [v,w]:adj[u]) if(v!=p){
  81.         if(w==1) continue;
  82.         if(dfsa(v,u)) return true;
  83.         if(dB[u]==INF && dB[v]==INF) return true;
  84.     }
  85.     return false;
  86. }
  87. bool dfsb(int u, int p=-1){
  88.     if(dB[u]>=dA[u]) return false;
  89.     for(auto [v,w]:adj[u]) if(v!=p){
  90.         if(w==0) continue;
  91.         if(dfsb(v,u)) return true;
  92.         if(dA[u]==INF && dA[v]==INF) return true;
  93.     }
  94.     return false;
  95. }
  96.  
  97. int dist(int u, int d=0, int p=-1){
  98.     if(u==b) return d;
  99.     for(auto [v,w]:adj[u]) if(v!=p){
  100.         int tmp=dist(v,d+1,u);
  101.         if(tmp!=-1) return tmp;
  102.     }
  103.     return -1;
  104. }
  105.  
  106. void solve(){
  107.     cin>>n>>a>>b;
  108.     FOR(i,1,n-1){
  109.         int x,y; string c; cin>>x>>y>>c;
  110.         int t;
  111.         if(c=="plava") t=0;
  112.         else if(c=="crvena") t=1;
  113.         else if(c=="magenta") t=2;
  114.         else assert(0);
  115.         adj[x].eb(y,t); adj[y].eb(x,t);
  116.     }
  117.  
  118.     bfsa();
  119.     bfsb();
  120.  
  121.     if(cntA==1) return cout<<"Marin",void();
  122.     if(cntB==1) return cout<<"Paula",void();
  123.  
  124.     int s=dist(a);
  125.     if(s%2==0){
  126.         if(dfsb(b)) cout<<"Magenta";
  127.         else cout<<"Paula";
  128.     } else{
  129.         if(dfsa(a)) cout<<"Magenta";
  130.         else cout<<"Marin";
  131.     }
  132. }
  133.  
  134. int32_t main() {
  135.     #define task "test"
  136.     if(fopen(task".inp", "r")){
  137.         freopen(task".inp", "r", stdin);
  138.         freopen(task".out", "w", stdout);
  139.     }
  140.     cin.tie(0)->sync_with_stdio(0);
  141.  
  142.     int tc = 1; // cin >> tc;
  143.     FOR(i, 1, tc){
  144.         solve();
  145.     }
  146. }
Success #stdin #stdout 0.01s 6008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Paula
https://ideone.com/ifIMDW
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!