#include <bits/stdc++.h>
using namespace std;
#define EMT ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 2e18;
const double EPS = 1e-9;
const int N = 1e5 + 25, LGN = 20;
int dep[N], anc[LGN][N], pat[N], cnt[N][4];
bool vis[N], can[N];
vector<pair<int, int>> edge[N];
void dfs(int u) {
//cerr << u << '\n';
for(const auto &[v, t] : edge[u]) {
if(v != anc[0][u]) {
anc[0][v] = u;
dep[v] = dep[u] + 1;
pat[v] = t;
dfs(v);
}
}
}
void dfs(int u, int w) {
vis[u] = 1;
for(const auto &[v, t] : edge[u])
if(!vis[v] && (t >> w & 1))
dfs(v, w);
}
void go(int u, int w) {
can[u] = 1;
for(const auto &[v, t] : edge[u])
if(!can[v] && (t >> w & 1))
go(v, w);
}
void build(int n) {
for(int i = 1; i < LGN; i++)
for(int j = 1; j <= n; j++)
anc[i][j] = anc[i - 1][anc[i - 1][j]];
}
int lca(int a, int b) {
if(dep[a] < dep[b])
swap(a, b);
//cout << "here " << a << ' ' << b << '\n';
for(int i = LGN - 1, w = dep[a] - dep[b]; ~i; i--)
if(w >> i & 1)
a = anc[i][a];
//cout << "here " << a << ' ' << b << '\n';
if(a == b)
return a;
for(int i = LGN - 1; ~i; i--)
if(anc[i][a] != anc[i][b])
a = anc[i][a], b = anc[i][b];
return anc[0][a];
}
inline int dis(int a, int b) { return dep[a] + dep[b] - 2 * dep[lca(a, b)]; }
signed main() { EMT
int n;
cin >> n;
int a, b;
cin >> a >> b;
vis[0] = 1;
for(int i = 1, a, b, t; i < n; i++) {
cin >> a >> b;
string s;
cin >> s;
if(s[0] == 'p')
t = 1;
if(s[0] == 'c')
t = 2;
if(s[0] == 'm')
t = 3;
edge[a].push_back({b, t});
cnt[a][t]++;
edge[b].push_back({a, t});
cnt[b][t]++;
}
if(cnt[a][1] + cnt[a][3] == 0)
return cout << "Marin\n", 0;
if(cnt[b][2] + cnt[b][3] == 0)
return cout << "Paula\n", 0;
dfs(a);
if(dep[b] & 1) {
memset(anc[0], 0, sizeof anc[0]);
memset(pat, 0, sizeof pat);
memset(dep, 0, sizeof dep);
//cerr << "here\n";
dfs(b);
dfs(b, 1);
go(a, 0);
build(n);
//for(int i = 1; i <= n; i++)
//cout << lca(i, a) << " \n"[i == n];
bool ok = 0;
for(int i = 1; i <= n; i++)
ok |= (pat[i] & 1) && lca(i, a) != b && !vis[anc[0][i]] && can[i] && (!vis[lca(i, a)] || dis(a, i) <= dep[i]);
cout << (ok ? "Magenta" : "Marin") << '\n';
}// Lost or draw
else {
memset(anc[0], 0, sizeof anc[0]);
memset(pat, 0, sizeof pat);
memset(dep, 0, sizeof dep);
//cerr << "owo\n";
dfs(a);
dfs(a, 0);
go(b, 1);
build(n);
bool ok = 0;
for(int i = 1; i <= n; i++)
ok |= (pat[i] & 2) && lca(i, b) != a && !vis[anc[0][i]] && can[i] && (!vis[lca(i, b)] || dis(b, i) < dep[i]);
cout << (ok ? "Magenta" : "Paula") << '\n';
}// Win or draw
}
/*
5
3 5
1 2 magenta
1 3 magenta
2 4 plava
2 5 crvena
5
1 4
2 1 plava
1 3 crvena
5 2 plava
4 1 magenta
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:82:12: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
82 | cnt[b][t]++;
| ~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3968 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3948 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
16912 KB |
Output is correct |
| 2 |
Correct |
137 ms |
16804 KB |
Output is correct |
| 3 |
Correct |
118 ms |
16748 KB |
Output is correct |
| 4 |
Correct |
109 ms |
16748 KB |
Output is correct |
| 5 |
Correct |
116 ms |
16876 KB |
Output is correct |
| 6 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
3948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3968 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3948 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
