제출 #375505

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375505		SeDunion	Magenta (COCI21_magenta)	C++17	30 / 110	148 ms	74348 KiB

Main

#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];
 
void dfs(int v, int type, int Rpoint, bool &R, int &dist, int p = -1, int cur_dist = 0) {
	if (Rpoint == v) {
		R = true;
		dist = cur_dist;
	}
	for (auto [to, w] : g[v]) if (to != p && (w == BOTH || w == type)) {
		dfs(to, type, Rpoint, R, dist, v, cur_dist + 1);
	}
}
 
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;
	dfs(a, FIRST, b, aR, ad);
	dfs(b, SECOND, a, bR, bd);
	{
		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;
		}
	}
	if (aR == false && bR == false) {
		cout << "Magenta";
		return 0;
	}
	dist = (aR ? ad : bd);
	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;
					}
					d[to] = t + 1;
					Q[t].push(to);
					if (t == 0 && w == FIRST) {
						int cnt = 0;
						for (auto [ew, w] : g[to]) {
							cnt += w == FIRST || w == BOTH;
						}
						if (cnt > 1) {
							aE = true;
						}
					}
					if (t == 1 && w == SECOND) {
						int cnt = 0;
						for (auto [ew, w] : g[to]) {
							cnt += w == SECOND || w == BOTH;
						}
						if (cnt > 1) {
							bE = true;
						}
					}
				}
			}
		}
		if (any == false) {
			break;
		}
	}
	//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: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50