oj.uz

답안 #375548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375548 2021-03-09T14:03:39 Z SeDunion Magenta (COCI21_magenta) C++17
30 / 110
 135 ms 74476 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];
 
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) {
			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);
		}
	}
}
 
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);
	dfs(b, SECOND, a, bR, bc, 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;
		}
	}
	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) {
						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) {
						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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 69996 KB Output is correct
2 Correct 54 ms 69996 KB Output is correct
3 Correct 57 ms 69996 KB Output is correct
4 Correct 55 ms 69996 KB Output is correct
5 Incorrect 54 ms 69996 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 74476 KB Output is correct
2 Correct 128 ms 74220 KB Output is correct
3 Correct 126 ms 74220 KB Output is correct
4 Correct 135 ms 74348 KB Output is correct
5 Correct 132 ms 74432 KB Output is correct
6 Correct 55 ms 69996 KB Output is correct
7 Correct 54 ms 70144 KB Output is correct
8 Correct 54 ms 69996 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 69996 KB Output is correct
2 Correct 54 ms 69996 KB Output is correct
3 Correct 57 ms 69996 KB Output is correct
4 Correct 55 ms 69996 KB Output is correct
5 Incorrect 54 ms 69996 KB Output isn't correct
6 Halted 0 ms 0 KB -