#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int NN = 1e6 + 5;
const int mo = 1e9 + 7;
const ld eps = 1e-9;
ll n, a, b;
vector<ll> v[NN];
vector<ll> w[NN];
ll A = 0;
ll B = 0;
ll dis[4][NN];
ll rg[4];
void dfs(ll pos, ll par, ll jen, ll jar)
{
// rg[jen]++;
// if(jen == 2)
// rg[2]++;
dis[jen][pos] = jar;
for(ll i = 0; i < v[pos].size(); i++)
if((v[pos][i] != par) && (w[pos][i] & jen))
dfs(v[pos][i], pos, jen, jar + 1);
}
void dfs1(ll pos, ll par)
{
if(dis[2][pos] < dis[1][pos])
return ;
// rg[1]++;
if(dis[2][pos] == 1e18)
{
for(ll i = 0; i < v[pos].size(); i++)
if(dis[2][v[pos][i]] == 1e18)
A = 1;
for(ll i = 0; i < v[pos].size(); i++)
if((dis[2][v[pos][i]] % 2) == (dis[1][v[pos][i]] % 2))
A = 1;
}
for(ll i = 0; i < v[pos].size(); i++)
if((v[pos][i] != par) && (w[pos][i] & 1))
dfs1(v[pos][i], pos);
}
void dfs2(ll pos, ll par)
{
if(dis[1][pos] <= dis[2][pos])
return ;
// rg[2]++;
if(dis[1][pos] == 1e18)
{
for(ll i = 0; i < v[pos].size(); i++)
if(dis[1][v[pos][i]] == 1e18)
B = 1;
for(ll i = 0; i < v[pos].size(); i++)
if((dis[1][v[pos][i]] % 2) != (dis[2][v[pos][i]] % 2))
B = 1;
}
for(ll i = 0; i < v[pos].size(); i++)
if((v[pos][i] != par) && (w[pos][i] & 2))
dfs2(v[pos][i], pos);
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> a >> b;
for(ll i = 1; i <= n; i++)
{
dis[1][i] = 1e18;
dis[2][i] = 1e18;
}
for(ll i = 1; i < n; i++)
{
ll ta, tb, tc = 3;
string s;
cin >> ta >> tb >> s;
if(s == "plava")tc = 1;
else if(s == "crvena")tc = 2;
v[ta].pb(tb);
w[ta].pb(tc);
v[tb].pb(ta);
w[tb].pb(tc);
}
dfs(a, a, 1, 0);
dfs(b, b, 2, 0);
dfs(a, a, 3, 0);
dfs1(a, a);
dfs2(b, b);
// if(A == 0 && B == 0)
// {
// if(dis[1][b])
// }
// cout << rg[1] << " " << rg[2] << "\n";
// cout << A << " " << B << " " << dis[3][b] << "@\n" << "\n";
if(rg[1] == 1 || n == 2)
cout << "Marin\n";
else
if(rg[2] == 1)
cout << "Paula\n";
else
if(((dis[3][b] % 2 == 0) && (dis[3][b] != 1e18)) && (B == 0))
cout << "Paula\n";
else
if((dis[3][b] % 2 == 1) && (A == 0))
cout << "Marin\n";
else
cout << "Magenta\n";
}
Compilation message
Main.cpp: In function 'void dfs(ll, ll, ll, ll)':
Main.cpp:25:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(ll i = 0; i < v[pos].size(); i++)
| ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs1(ll, ll)':
Main.cpp:36:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(ll i = 0; i < v[pos].size(); i++)
| ~~^~~~~~~~~~~~~~~
Main.cpp:39:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(ll i = 0; i < v[pos].size(); i++)
| ~~^~~~~~~~~~~~~~~
Main.cpp:43:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(ll i = 0; i < v[pos].size(); i++)
| ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs2(ll, ll)':
Main.cpp:54:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(ll i = 0; i < v[pos].size(); i++)
| ~~^~~~~~~~~~~~~~~
Main.cpp:57:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(ll i = 0; i < v[pos].size(); i++)
| ~~^~~~~~~~~~~~~~~
Main.cpp:61:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(ll i = 0; i < v[pos].size(); i++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
47340 KB |
Output is correct |
| 2 |
Correct |
28 ms |
47340 KB |
Output is correct |
| 3 |
Correct |
28 ms |
47340 KB |
Output is correct |
| 4 |
Incorrect |
28 ms |
47340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
57196 KB |
Output is correct |
| 2 |
Correct |
155 ms |
57344 KB |
Output is correct |
| 3 |
Correct |
158 ms |
57196 KB |
Output is correct |
| 4 |
Correct |
155 ms |
57196 KB |
Output is correct |
| 5 |
Correct |
160 ms |
57196 KB |
Output is correct |
| 6 |
Correct |
28 ms |
47340 KB |
Output is correct |
| 7 |
Correct |
28 ms |
47340 KB |
Output is correct |
| 8 |
Correct |
27 ms |
47340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
47340 KB |
Output is correct |
| 2 |
Correct |
28 ms |
47340 KB |
Output is correct |
| 3 |
Correct |
28 ms |
47340 KB |
Output is correct |
| 4 |
Incorrect |
28 ms |
47340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
