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;
const int N = 1e5 + 5, INF = 1e9 + 5;
int n, a, b, x, y, adist[N], bdist[N];
string str;
char c;
vector<pair<int, char>> tree[N];
bool isainf, isbinf;
void dfsa(int v, int p, int d){
adist[v] = d;
for(auto e : tree[v]){
if(e.first != p && e.second != 'R'){
dfsa(e.first, v, d + 1);
}
}
}
void dfsb(int v, int p, int d){
bdist[v] = d;
for(auto e : tree[v]){
if(e.first != p && e.second != 'B'){
dfsb(e.first, v, d + 1);
}
}
}
void checka(int v, int p, int d){
for(auto e : tree[v]){
if(e.first != p && e.second != 'R'){
if(bdist[e.first] > d - 1 || bdist[e.first] % 2 != (d - 1) % 2){
checka(e.first, v, d + 1);
if(bdist[v] % 2 != ((d + 1) - 1) % 2) isainf = true;
}
}
}
}
void checkb(int v, int p, int d){
for(auto e : tree[v]){
if(e.first != p && e.second != 'B'){
if(adist[e.first] > d || adist[e.first] % 2 != d % 2){
checkb(e.first, v, d + 1);
if(adist[v] % 2 != (d + 1) % 2) isbinf = true;
}
}
}
}
int dist(int v, int p, int d){
if(v == b) return d;
else{
int mx = -1;
for(auto e : tree[v]){
if(e.first != p){
mx = max(mx, dist(e.first, v, d + 1));
}
}
return mx;
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> n;
cin >> a >> b;
for(int i = 1; i <= n - 1; i++){
cin >> x >> y >> str;
if(str == "plava") c = 'B';
else if(str == "crvena") c = 'R';
else if(str == "magenta") c = 'M';
tree[x].push_back({y, c});
tree[y].push_back({x, c});
}
fill(adist, adist + N, INF), fill(bdist, bdist + N, INF);
dfsa(a, 0, 0), dfsb(b, 0, 0);
checka(a, 0, 1), checkb(b, 0, 1);
if(isainf && isbinf) cout << "Magenta";
else if(isainf) cout << "Paula";
else if(isbinf) cout << "Marin";
else{
int ans = dist(a, 0, 0);
if(adist[b] == INF && bdist[a] == INF) cout << "Marin";
else if(ans == -1) cout << "Marin";
else if(ans % 2 == 0) cout << "Paula";
else cout << "Marin";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |