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;
typedef long long ll;
const int N = 1e5 + 1;
const int INF = 1e9 + 7;
struct Edge{
int u, v, c;
Edge(int _u, int _v, int _c){
u = _u;
v = _v;
c = _c;
}
};
int n, a, b;
vector<Edge> adj[N];
int dist[N], distFromA[N], distFromB[N];
bool vst[N];
int dfs(int u, int p, int dist[], int type){
if (p == -1)
dist[u] = 0;
int res = 1;
for(Edge e : adj[u])
if (e.v != p && (e.c & type)){
dist[e.v] = dist[u] + 1;
res += dfs(e.v, u, dist, type);
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> a >> b;
for(int i = 1; i < n; i++){
int u, v, c;
string s;
cin >> u >> v >> s;
if (s == "plava")
c = 1;
else if (s == "crvena")
c = 2;
else
c = 3;
adj[u].push_back(Edge(u, v, c));
adj[v].push_back(Edge(v, u, c));
}
for(int i = 1; i <= n; i++)
dist[i] = distFromA[i] = distFromB[i] = INF;
dfs(a, -1, dist, 3);
int numA = dfs(a, -1, distFromA, 1);
int numB = dfs(b, -1, distFromB, 2);
if (numA == 1){
cout << "Marin\n";
return 0;
}
if (numB == 1){
cout << "Paula\n";
return 0;
}
if (dist[b] % 2 == 0){
queue<int> qu;
vst[b] = 1;
qu.push(b);
while(!qu.empty()){
int u = qu.front();
qu.pop();
for(Edge e : adj[u]){
int v = e.v;
int c = e.c;
if (distFromB[v] < distFromA[v] && !vst[v] && (c & 2)){
vst[v] = 1;
qu.push(v);
}
}
}
for(int i = 1; i <= n; i++)
vst[i] &= (distFromA[i] == INF);
for(int u = 1; u <= n; u++)
for(Edge e : adj[u])
if (vst[u] && vst[e.v]){
cout << "Magenta";
return 0;
}
cout << "Paula";
} else {
queue<int> qu;
vst[a] = 1;
qu.push(a);
while(!qu.empty()){
int u = qu.front();
qu.pop();
for(Edge e : adj[u]){
int v = e.v;
int c = e.c;
if (distFromA[v] <= distFromB[v] && !vst[v] && (c & 1)){
vst[v] = 1;
qu.push(v);
}
}
}
for(int i = 1; i <= n; i++)
vst[i] &= (distFromB[i] == INF);
for(int u = 1; u <= n; u++)
for(Edge e : adj[u])
if (vst[u] && vst[e.v]){
cout << "Magenta";
return 0;
}
cout << "Marin";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |