Submission #375213

#	Time	Username	Problem	Language	Result	Execution time	Memory
375213		SeDunion	Magenta (COCI21_magenta)	C++17	0 / 110	324 ms	524292 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 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;
	dfs(a, FIRST, b, aR, dist);
	dfs(b, SECOND, a, bR, dist);
	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) {
					d[to] = t + 1;
					Q[t].push(to);
					if (t == 0 && w == FIRST) {
						aE = true;
					}
					if (t == 1 && w == SECOND) {
						bE = true;
					}
				}
			}
		}
		if (any == false) {
			break;
		}
	}
	//cerr << aR << " " << bR << " " << aE << " " << bE << endl;
	if (dist & 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: 0 / 30
• Subtask 3: 0 / 50