| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 512324 |
2022-01-16T09:23:30 Z |
kartel |
Magenta (COCI21_magenta) |
C++14 |
|
139 ms |
9784 KB |
#include <bits/stdc++.h>
#define blue 0
#define red 1
#define purple 2
#define pb push_back
#define F first
#define S second
#define sz(x) (int)x.size()
using namespace std;
const int N = 2e5 + 500;
int n;
vector <pair <int, int> > g[N];
bool is_end[N];
bool can[N];
void bfs(int start, int bad_color, vector <int> &d) {
for (int i = 1; i <= n; i++) {
d[i] = 1e9;
}
queue <int> q;
q.push(start);
d[start] = 0;
while (sz(q)) {
int v = q.front(); q.pop();
for (auto to : g[v]) {
int u = to.F;
int clr = to.S;
if (clr == bad_color || d[u] != 1e9) {
continue;
}
d[u] = d[v] + 1;
q.push(u);
}
}
}
int main() {
int a, b;
cin >> n;
cin >> a >> b;
for (int i = 1; i < n; i++) {
int u, v;
string c;
cin >> u >> v >> c;
if (c == "plava") {
g[u].pb({v, blue});
g[v].pb({u, blue});
} else {
if (c == "crvena") {
g[u].pb({v, red});
g[v].pb({u, red});
} else {
g[u].pb({v, purple});
g[v].pb({u, purple});
}
}
}
vector <int> da(n + 1);
vector <int> db(n + 1);
bfs(a, red, da);
bfs(b, blue, db);
bool bada = 1;
for (auto to : g[a]) {
int i = to.F;
bada &= (da[i] == 1e9 || da[i] > db[i]);
}
if (bada) {
cout << "Marin";
return 0;
}
bool badb = 1;
for (auto to : g[b]) {
int i = to.F;
badb &= (db[i] == 1e9);
}
if (badb) {
cout << "Paula";
return 0;
}
if (da[b] != 1e9 && (da[b] % 2 == 0 || db[a] == 1e9)) {
/// first player go to the second
bool both = 0;
/// mark all vertices v, in that the second player can stay always(v -> u, u -> v, where u is adjacent of v)
for (int i = 1; i <= n; i++) {
int cnt_good = 0;
for (auto to : g[i]) {
int u = to.F;
int clr = to.S;
cnt_good += (clr != blue);
}
is_end[i] = (cnt_good == 1);
}
queue <int> q;
q.push(b);
while (sz(q)) {
int v = q.front(); q.pop();
can[v] = 1;
for (auto to : g[v]) {
int u = to.F;
if (db[u] == 1e9) {
continue;
}
if (db[u] == db[v] + 1 && db[u] < da[u]) {
q.push(u);
}
}
}
/// Can we have some vertice v, in that we can jump (u -> v, v -> u) and the first player can't stop him in the vertice v
for (int i = 1; i <= n; i++) {
if (!can[i]) {
continue;
}
bool have = 0;
for (auto to : g[i]) {
if (!can[to.F]) {
continue;
}
have |= (is_end[to.F] && (da[to.F] == 1e9 || da[to.F] > db[to.F]));
}
if (have && da[i] > db[i] && (da[i] - db[i]) % 2 != 0) {
both = 1;
}
}
/// Can we run from the component of the first player?
for (int i = 1; i <= n; i++) {
bool have = 0;
if (!can[i]) {
continue;
}
for (auto to : g[i]) {
int u = to.F;
if (!can[u]) {
continue;
}
if (db[u] < da[u] && db[u] + 1 == db[i]) {
have = 1;
}
}
for (auto to : g[i]) {
int u = to.F;
if (!can[u]) {
continue;
}
if (have && da[i] == 1e9 && da[u] == 1e9 && db[i] + 1 == db[u]) {
both = 1;
}
}
}
if (both) {
cout << "Magenta";
} else {
cout << "Paula";
}
return 0;
}
if (db[a] != 1e9 && (db[a] % 2 || da[b] == 1e9)) {
/// second player go to the first
bool both = 0;
queue <int> q;
q.push(a);
while (sz(q)) {
int v = q.front(); q.pop();
can[v] = 1;
for (auto to : g[v]) {
int u = to.F;
if (da[u] == 1e9) {
continue;
}
if (da[u] == da[v] + 1 && da[u] <= db[u]) {
q.push(u);
}
}
}
/// mark all vertices v, in that the first player can stay always(v -> u, u -> v, where u is adjacent of v)
for (int i = 1; i <= n; i++) {
if (!can[i]) {
continue;
}
int cnt_good = 0;
for (auto to : g[i]) {
int u = to.F;
int clr = to.S;
if (!can[u]) {
continue;
}
cnt_good += (clr != red);
}
is_end[i] = (cnt_good == 1);
}
/// Can we have some vertice v, in that we can jump (u -> v, v -> u) and the second player can't stop him in the vertice v
for (int i = 1; i <= n; i++) {
bool have = 0;
if (!can[i]) {
continue;
}
for (auto to : g[i]) {
have |= (is_end[to.F] && (db[to.F] >= da[to.F] || db[to.F] == 1e9) && da[to.F] != 1e9);
}
if (have && db[i] >= da[i] && (db[i] - da[i]) % 2 == 0 && da[i] != 1e9) {
both = 1;
}
}
/// Can we run from the component of the second player?
for (int i = 1; i <= n; i++) {
bool have = 0;
if (!can[i]) {
continue;
}
for (auto to : g[i]) {
int u = to.F;
if (!can[u]) {
continue;
}
if (da[u] <= db[u] && db[u] != 1e9 && da[u] + 1 == da[i]) {
have = 1;
}
}
for (auto to : g[i]) {
int u = to.F;
if (!can[u]) {
continue;
}
if (have && db[i] == 1e9 && db[u] == 1e9 && da[i] + 1 == da[u]) {
both = 1;
}
}
}
if (both) {
cout << "Magenta";
} else {
cout << "Marin";
}
return 0;
}
cout << "Magenta";
}
/*
5
3 5
4 2 crvena
3 5 plava
1 5 magenta
4 1 magenta
5
2 1
1 2 magenta
2 3 magenta
3 4 magenta
3 5 magenta
12
6 9
1 2 magenta
2 3 magenta
3 4 magenta
3 5 magenta
2 6 magenta
1 7 crvena
7 8 magenta
7 9 magenta
8 10 magenta
9 11 magenta
9 12 magenta
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:91:21: warning: unused variable 'u' [-Wunused-variable]
91 | int u = to.F;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4940 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
9784 KB |
Output is correct |
| 2 |
Correct |
104 ms |
9700 KB |
Output is correct |
| 3 |
Correct |
139 ms |
9764 KB |
Output is correct |
| 4 |
Correct |
104 ms |
9692 KB |
Output is correct |
| 5 |
Correct |
110 ms |
9748 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4964 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4940 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
