| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 512380 |
2022-01-16T10:12:55 Z |
kartel |
Magenta (COCI21_magenta) |
C++14 |
|
142 ms |
11928 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;
const int Ns = 105;
int n;
vector <pair <int, int> > g[N];
bool is_end[N];
bool can[N];
vector <pair <int, int> > gr[Ns][Ns][2];
int cnt[Ns][Ns][2];
bool win[Ns][Ns][2], lose[Ns][Ns][2];
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);
}
}
}
void brute(int a, int b) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
for (int par = 0; par < 2; par++) {
if (par) {
for (auto to : g[b]) {
int u = to.F, color = to.S;
if (color != blue) {
gr[a][u][par ^ 1].pb({a, b});
cnt[a][b][par]++;
}
}
} else {
for (auto to : g[a]) {
int u = to.F, color = to.S;
if (color != red) {
gr[u][b][par ^ 1].pb({a, b});
cnt[a][b][par]++;
}
}
}
}
}
}
queue <pair <pair <int, int>, int> > q;
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
for (int par = 0; par < 2; par++) {
if (a == b) {
win[a][b][par] = 1;
q.push({{a, b}, par});
} else {
if (!cnt[a][b][par]) {
q.push({{a, b}, par});
lose[a][b][par] = 1;
}
}
}
}
}
while (sz(q)) {
int a = q.front().F.F, b = q.front().F.S, par = q.front().S; q.pop();
if (lose[a][b][par]) {
for (auto p : gr[a][b][par]) {
int na = p.F;
int nb = p.S, npar = par ^ 1;
if (!win[na][nb][npar]) {
q.push({{na, nb}, npar});
win[na][nb][npar] = 1;
}
}
} else {
for (auto p : gr[a][b][par]) {
int na = p.F;
int nb = p.S, npar = par ^ 1;
cnt[na][nb][npar]--;
if (!cnt[na][nb][npar]) {
q.push({{na, nb}, npar});
lose[na][nb][npar] = 1;
}
}
}
}
cout << (win[a][b][0] ? "Paula" : (lose[a][b][0] ? "Marin" : "Magenta"));
exit(0);
}
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});
}
}
}
if (n <= 100) {
brute(a, b);
}
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)
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);
}
}
}
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 != blue);
}
is_end[i] = (cnt_good == 1);
}
/// 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]) {
if (!can[to.F]) {
continue;
}
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 plava
7 8 magenta
7 9 magenta
8 10 magenta
9 11 magenta
9 12 magenta
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 8 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 9 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 10 |
Correct |
5 ms |
6144 KB |
Output is correct |
| 11 |
Correct |
7 ms |
6220 KB |
Output is correct |
| 12 |
Correct |
4 ms |
6220 KB |
Output is correct |
| 13 |
Correct |
4 ms |
6220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
10240 KB |
Output is correct |
| 2 |
Correct |
142 ms |
10256 KB |
Output is correct |
| 3 |
Correct |
112 ms |
10256 KB |
Output is correct |
| 4 |
Correct |
104 ms |
10228 KB |
Output is correct |
| 5 |
Correct |
101 ms |
10184 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5500 KB |
Output is correct |
| 8 |
Correct |
3 ms |
5452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 8 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 9 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 10 |
Correct |
5 ms |
6144 KB |
Output is correct |
| 11 |
Correct |
7 ms |
6220 KB |
Output is correct |
| 12 |
Correct |
4 ms |
6220 KB |
Output is correct |
| 13 |
Correct |
4 ms |
6220 KB |
Output is correct |
| 14 |
Correct |
109 ms |
10240 KB |
Output is correct |
| 15 |
Correct |
142 ms |
10256 KB |
Output is correct |
| 16 |
Correct |
112 ms |
10256 KB |
Output is correct |
| 17 |
Correct |
104 ms |
10228 KB |
Output is correct |
| 18 |
Correct |
101 ms |
10184 KB |
Output is correct |
| 19 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 20 |
Correct |
3 ms |
5500 KB |
Output is correct |
| 21 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 22 |
Correct |
4 ms |
5528 KB |
Output is correct |
| 23 |
Correct |
3 ms |
5456 KB |
Output is correct |
| 24 |
Correct |
4 ms |
5456 KB |
Output is correct |
| 25 |
Correct |
4 ms |
5456 KB |
Output is correct |
| 26 |
Correct |
4 ms |
5524 KB |
Output is correct |
| 27 |
Correct |
4 ms |
5456 KB |
Output is correct |
| 28 |
Correct |
3 ms |
5456 KB |
Output is correct |
| 29 |
Correct |
3 ms |
5456 KB |
Output is correct |
| 30 |
Correct |
4 ms |
5456 KB |
Output is correct |
| 31 |
Correct |
113 ms |
11848 KB |
Output is correct |
| 32 |
Correct |
98 ms |
11852 KB |
Output is correct |
| 33 |
Correct |
118 ms |
11928 KB |
Output is correct |
| 34 |
Correct |
97 ms |
11776 KB |
Output is correct |
