This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
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 build(int n) {
for(int i = 0; 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);
for(int i = LGN - 1, w = dep[a] - dep[b]; ~i; i--)
if(w >> i & 1)
a = anc[i][a];
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] - dep[lca(a, b)]; }
signed main() { EMT
int n;
cin >> n;
int a, b;
cin >> a >> b;
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]++;
}
dfs(a);
//for(int i = 1; i <= n; i++)
//cout << dep[i] << " \n"[i == n];
if(dep[b] & 1) {
//cerr << "here\n";
dfs(b);
dfs(b, 1);
build(n);
bool ok = 0;
for(int i = 1; i <= n; i++)
ok |= (pat[i] == 1) && (cnt[i][1] + cnt[i][3] > 1) && lca(i, a) != b && (!vis[anc[0][i]] || dis(a, anc[0][i]) <= dep[anc[0][i]]);
cout << (ok ? "Magenta" : "Marin") << '\n';
}// Lost or draw
else {
//cerr << "owo\n";
dfs(a);
dfs(a, 0);
build(n);
bool ok = 0;
for(int i = 1; i <= n; i++)
ok |= (pat[i] == 2) && (cnt[i][2] + cnt[i][3] > 1) && lca(i, b) != a && (!vis[anc[0][i]] || dis(b, anc[0][i]) < dep[anc[0][i]]);
cout << (ok ? "Magenta" : "Paula") << '\n';
}// Win or draw
}
/*
5
3 5
1 2 magenta
1 3 magenta
2 4 plava
2 5 crvena
*/
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:73:12: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
73 | cnt[b][t]++;
| ~~~~~~~~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |