#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
map <string, int> col = {
{"plava", 0},
{"crvena", 1},
{"magenta", 2}
};
const int N = 1e5 + 100;
int n;
int dist[2][N];
vector <pair <int, int> > g[N];
vector <string> names = {"Paula", "Marin", "Magenta"};
int move_to[2];
vector <int> s;
void print(int a)
{
cout << names[a];
}
int len;
void dfs(int v, int i, int p = -1)
{
for(int j = 0; j < g[v].size(); j++)
{
int to = g[v][j].X;
int type = g[v][j].Y;
if(to == p)
{
continue;
}
if(to == s[i ^ 1])
{
len = dist[i][v] + 1;
}
if(type != (i ^ 1))
{
dist[i][to] = dist[i][v] + 1;
dfs(to, i, v);
}
}
}
int val;
bool funct(int v, int p =-1)
{
bool fl = 0;
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].X;
int w = g[v][i].Y;
if(to == p || w == (val ^ 1) || dist[val ^ 1][to] != 1e9 && dist[val][to] >= dist[val ^ 1][to])
{
continue;
}
if(dist[val ^ 1][v]== 1e9 || dist[val ^ 1][v] == 1e9)
{
return 1;
}
fl |= funct(to, v);
}
return fl;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
int a, b;
cin >> a >> b;
a--;
b--;
s = {a, b};
for(int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
u--;
v--;
string s;
cin >> s;
int type = col[s];
g[u].push_back({v, type});
g[v].push_back({u, type});
if(type != 1 && (u == a && v != b || v == a && u != b))
{
move_to[0] = 1;
}
if(type != 0 && (u == b || v == b))
{
move_to[1] = 1;
}
}
if(!move_to[0])
{
print(1);
return 0;
}
if(!move_to[1])
{
print(0);
return 0;
}
for(int i = 0; i < 2; i++)
{
int st = s[i];
fill(dist[i], dist[i] + N, 1e9);
dist[i][s[i]] = 0;
dfs(s[i], i);
}
val = (len + 1) % 2;
if(funct(s[val], -1))
{
print(2);
return 0;
}
print(1 - val);
return 0;
}
Compilation message
Main.cpp: In function 'void dfs(int, int, int)':
Main.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int j = 0; j < g[v].size(); j++)
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'bool funct(int, int)':
Main.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i = 0; i < g[v].size(); i++)
| ~~^~~~~~~~~~~~~
Main.cpp:51:66: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
51 | if(to == p || w == (val ^ 1) || dist[val ^ 1][to] != 1e9 && dist[val][to] >= dist[val ^ 1][to])
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:85:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
85 | if(type != 1 && (u == a && v != b || v == a && u != b))
| ~~~~~~~^~~~~~~~~
Main.cpp:106:13: warning: unused variable 'st' [-Wunused-variable]
106 | int st = s[i];
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3436 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3436 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
3436 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
7148 KB |
Output is correct |
| 2 |
Correct |
77 ms |
7276 KB |
Output is correct |
| 3 |
Correct |
92 ms |
7404 KB |
Output is correct |
| 4 |
Correct |
87 ms |
7256 KB |
Output is correct |
| 5 |
Correct |
89 ms |
7148 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3436 KB |
Output is correct |
| 8 |
Correct |
3 ms |
3436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3436 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3436 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
3436 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
