#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;
const int BOTH = 2;
const int FIRST = 0;
const int SECOND = 1;
vector<pair<int,int>>g[N];
int d[N];
queue<int>Q[N];
void dfs(int v, int type, int Rpoint, bool &R, int &dist, int p = -1, int cur_dist = 0) {
if (Rpoint == v) {
R = true;
dist = cur_dist;
}
for (auto [to, w] : g[v]) if (to != p && (w == BOTH || w == type)) {
dfs(to, type, Rpoint, R, dist, v, cur_dist + 1);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
int a, b;
cin >> a >> b;
for (int i = 1 ; i < n ; ++ i) {
int u, v;
string w;
cin >> u >> v >> w;
g[u].emplace_back(v, w == "magenta" ? BOTH : (w == "plava" ? FIRST : SECOND));
g[v].emplace_back(u, w == "magenta" ? BOTH : (w == "plava" ? FIRST : SECOND));
}
bool aR = false, bR = false;
int dist = 0;
dfs(a, FIRST, b, aR, dist);
dfs(b, SECOND, a, bR, dist);
if (aR == false && bR == false) {
cout << "Magenta";
return 0;
}
Q[0].push(a);
d[a] = 1;
Q[1].push(b);
d[b] = 2;
bool aE = false, bE = false;
queue<int>cur;
while (1) {
bool any = false;
for (int t = 0 ; t < 2 ; ++ t) {
while(Q[t].size()) {
cur.push(Q[t].front());
Q[t].pop();
}
while (cur.size()) {
any = 1;
int v = cur.front(); cur.pop();
//cout << v << " " << t << "\n";
for (auto [to, w] : g[v]) if (d[to] == 0) {
d[to] = t + 1;
Q[t].push(to);
if (t == 0 && w == FIRST) {
aE = true;
}
if (t == 1 && w == SECOND) {
bE = true;
}
}
}
}
if (any == false) {
break;
}
}
//cerr << aR << " " << bR << " " << aE << " " << bE << endl;
if (dist & 1) { // first player cannot move
if (aE == false && bR == true) {
cout << "Marin";
return 0;
}
cout << "Magenta";
return 0;
} else { // second player cannot move
if (bE == false && aR == true) {
cout << "Paula";
return 0;
}
cout << "Magenta";
return 0;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
303 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
324 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
303 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
