oj.uz

Submission #375567

# Submission time Handle Problem Language Result Execution time Memory
375567 2021-03-09T14:29:53 Z SeDunion Magenta (COCI21_magenta) C++17
110 / 110
 153 ms 75884 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 66;
 
const int BOTH = 2;
const int FIRST = 0;
const int SECOND = 1;
 
vector<pair<int,int>>g[N];
 
int d[N];
 
queue<int>Q[N];

int onpath[N];
 
void dfs(int v, int type, int Rpoint, bool &R, bool &comp, int &dist, int p = -1, int cur_dist = 0) {
	for (auto [to, w] : g[v]) {
		if (to == Rpoint) {
			if (type == FIRST) onpath[to] = 1;
			if (type == FIRST) onpath[v] = 1;
			comp = w != type && w != BOTH;
			R = true;
			dist = cur_dist + 1;
		}
		if (to != p && (w == BOTH || w == type)) {
			dfs(to, type, Rpoint, R, comp, dist, v, cur_dist + 1);
			if (type == FIRST) onpath[v] |= onpath[to];
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int a, b;
	cin >> a >> b;
	for (int i = 1 ; i < n ; ++ i) {
		int u, v;
		string w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w == "magenta" ? BOTH : (w == "plava" ? FIRST : SECOND));
		g[v].emplace_back(u, w == "magenta" ? BOTH : (w == "plava" ? FIRST : SECOND));
	}
	bool aR = false, bR = false;
	int dist = 0;
	int ad = 0, bd = 0;
	bool ac = 0, bc = 0;
	dfs(a, FIRST, b, aR, ac, ad);
	for (int i = 1 ; i <= n ; ++ i) {
		//if (onpath[i]) cout << i << " ";
		//if (i == n) cout << endl;
	}
	dfs(b, SECOND, a, bR, bc, bd);
	for (int i = 1 ; i <= n ; ++ i) {
		//if (onpath[i]) cout << i << " ";
		//if (i == n) cout << endl;
	}
	{
		bool hasa = false;
		for (auto [to, w] : g[a]) {
			if (to == b) continue;
			hasa |= w == FIRST || w == BOTH;
		}
		if (hasa == false) {
			cout << "Marin";
			return 0;
		}
	}
	{
		bool hasb = false;
		for (auto [to, w] : g[b]) {
			//if (to == a) continue;
			hasb |= w == SECOND || w == BOTH;
	}
		if (hasb == false) {
			cout << "Paula";
			return 0;
		}
	}
	dist = (aR ? ad : bd);
	if (aR == false && dist % 2 == 0) {
		cout << "Magenta";
		return 0;
	}
	if (aR == false && dist % 2 == 1) {
		cout << "Magenta";
		return 0;
	}
	if (aR == false && bR == false) {
		cout << "Magenta";
		return 0;
	}
	Q[0].push(a);
	d[a] = 1;
	Q[1].push(b);
	d[b] = 2;
	bool aE = false, bE = false;
	queue<int>cur;
	while (1) {
		bool any = false;
		for (int t = 0 ; t < 2 ; ++ t) {
			while(Q[t].size()) {
				cur.push(Q[t].front());
				Q[t].pop();
			}
			while (cur.size()) {
				any = 1;
				int v = cur.front(); cur.pop();
				//cout << v << " " << t << "\n";
				for (auto  [to, w] : g[v]) if (d[to] == 0) {
					if ((w == SECOND && t == 0) || (w == FIRST && t == 1)) {
						continue;
					}
					if (t == 0 && w == FIRST && onpath[to] == 0) {
						int cnt = 0;
						for (auto [ew, wi] : g[to]) {
							cnt += wi == FIRST || wi == BOTH;
						}
						if (cnt > 1) {
							//cout << "first " << v << " " << cnt << " " << a << endl;
							aE = true;
						}
					}
					if (t == 1 && w == SECOND && onpath[to] == 0) {
						int cnt = 0;
						for (auto [ew, wi] : g[to]) {
							cnt += wi == SECOND || wi == BOTH;
						}
						if (cnt > 1) {
							//cout << "second " << v << " " << cnt << " " << b << endl;
							bE = true;
						}
					}
					//cout << t << " " << v << " -> " << to << endl;
					d[to] = t + 1;
					Q[t].push(to);
				}
			}
		}
		if (any == false) {
			break;
		}
	}
	if (ac == true) {
		int cnt = 0;
		for (auto [to, w] : g[b]) {
			cnt += w == SECOND || w == BOTH;
		}
		if (cnt > 1) {
			bE = true;
		}
	}
	if (bc == true) {
		int cnt = 0;
		for (auto [to, w] : g[a]) {
			cnt += w == FIRST || w == BOTH;
		}
		if (cnt > 1) {
			aE = true;
		}
	}
	cerr << aR << " " << bR << " " << aE << " " << bE << endl;
	if (dist % 2 == 1) { // first player cannot move
		if (aE == false && bR == true) {
			cout << "Marin";
			return 0;
		}
		cout << "Magenta";
		return 0;
	} else { // second player cannot move
		if (bE == false && aR == true) {
			cout << "Paula";
			return 0;
		}
		cout << "Magenta";
		return 0;
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 70124 KB Output is correct
2 Correct 56 ms 69996 KB Output is correct
3 Correct 55 ms 69996 KB Output is correct
4 Correct 55 ms 69996 KB Output is correct
5 Correct 62 ms 70048 KB Output is correct
6 Correct 55 ms 70124 KB Output is correct
7 Correct 55 ms 69996 KB Output is correct
8 Correct 54 ms 69996 KB Output is correct
9 Correct 54 ms 69996 KB Output is correct
10 Correct 58 ms 69996 KB Output is correct
11 Correct 55 ms 70124 KB Output is correct
12 Correct 56 ms 70124 KB Output is correct
13 Correct 55 ms 70124 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 74604 KB Output is correct
2 Correct 143 ms 74604 KB Output is correct
3 Correct 142 ms 74632 KB Output is correct
4 Correct 133 ms 74604 KB Output is correct
5 Correct 136 ms 74604 KB Output is correct
6 Correct 55 ms 69996 KB Output is correct
7 Correct 55 ms 69996 KB Output is correct
8 Correct 56 ms 69996 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 70124 KB Output is correct
2 Correct 56 ms 69996 KB Output is correct
3 Correct 55 ms 69996 KB Output is correct
4 Correct 55 ms 69996 KB Output is correct
5 Correct 62 ms 70048 KB Output is correct
6 Correct 55 ms 70124 KB Output is correct
7 Correct 55 ms 69996 KB Output is correct
8 Correct 54 ms 69996 KB Output is correct
9 Correct 54 ms 69996 KB Output is correct
10 Correct 58 ms 69996 KB Output is correct
11 Correct 55 ms 70124 KB Output is correct
12 Correct 56 ms 70124 KB Output is correct
13 Correct 55 ms 70124 KB Output is correct
14 Correct 153 ms 74604 KB Output is correct
15 Correct 143 ms 74604 KB Output is correct
16 Correct 142 ms 74632 KB Output is correct
17 Correct 133 ms 74604 KB Output is correct
18 Correct 136 ms 74604 KB Output is correct
19 Correct 55 ms 69996 KB Output is correct
20 Correct 55 ms 69996 KB Output is correct
21 Correct 56 ms 69996 KB Output is correct
22 Correct 55 ms 69996 KB Output is correct
23 Correct 55 ms 70124 KB Output is correct
24 Correct 56 ms 70124 KB Output is correct
25 Correct 59 ms 69996 KB Output is correct
26 Correct 55 ms 70124 KB Output is correct
27 Correct 56 ms 70124 KB Output is correct
28 Correct 66 ms 69996 KB Output is correct
29 Correct 68 ms 69996 KB Output is correct
30 Correct 55 ms 69996 KB Output is correct
31 Correct 109 ms 75628 KB Output is correct
32 Correct 113 ms 75756 KB Output is correct
33 Correct 112 ms 75628 KB Output is correct
34 Correct 112 ms 75884 KB Output is correct