oj.uz

답안 #375380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375380 2021-03-09T10:20:30 Z SeDunion Magenta (COCI21_magenta) C++17
30 / 110
 147 ms 76396 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, 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) {
					if ((w == SECOND && t == 0) || (w == FIRST && t == 1)) {
						continue;
					}
					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 % 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 Incorrect 54 ms 69996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 74220 KB Output is correct
2 Correct 147 ms 76140 KB Output is correct
3 Correct 141 ms 76140 KB Output is correct
4 Correct 140 ms 76396 KB Output is correct
5 Correct 140 ms 76140 KB Output is correct
6 Correct 57 ms 69996 KB Output is correct
7 Correct 55 ms 69996 KB Output is correct
8 Correct 56 ms 70124 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 69996 KB Output isn't correct
2 Halted 0 ms 0 KB -