oj.uz

답안 #373298

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373298 2021-03-04T03:04:02 Z rk42745417 Magenta (COCI21_magenta) C++17
30 / 110
 137 ms 16748 KB 
#include <bits/stdc++.h>
using namespace std;

#define EMT ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 2e18;
const double EPS = 1e-9;

const int N = 1e5 + 25, LGN = 20;
int dep[N], anc[LGN][N], pat[N], cnt[N][4];
bool vis[N], can[N];
vector<pair<int, int>> edge[N];
void dfs(int u) { 
	//cerr << u << '\n';
	for(const auto &[v, t] : edge[u]) {
		if(v != anc[0][u]) {
			anc[0][v] = u;
			dep[v] = dep[u] + 1;
			pat[v] = t;
			dfs(v);
		}
	}
}
void dfs(int u, int w) {
	vis[u] = 1;
	for(const auto &[v, t] : edge[u])
		if(!vis[v] && (t >> w & 1))
			dfs(v, w);
}
void go(int u, int w) {
	can[u] = 1;
	for(const auto &[v, t] : edge[u])
		if(!can[v] && (t >> w & 1))
			go(v, w);
}
void build(int n) {
	for(int i = 1; i < LGN; i++)
		for(int j = 1; j <= n; j++)
			anc[i][j] = anc[i - 1][anc[i - 1][j]];
}
int lca(int a, int b) {
	if(dep[a] < dep[b])
		swap(a, b);
	//cout << "here " << a << ' ' << b << '\n';
	for(int i = LGN - 1, w = dep[a] - dep[b]; ~i; i--)
		if(w >> i & 1)
			a = anc[i][a];
	//cout << "here " << a <<  ' ' << b << '\n';
	if(a == b)
		return a;
	for(int i = LGN - 1; ~i; i--)
		if(anc[i][a] != anc[i][b])
			a = anc[i][a], b = anc[i][b];
	return anc[0][a];
}
inline int dis(int a, int b) { return dep[a] + dep[b] - 2 * dep[lca(a, b)]; }

signed main() { EMT
	int n;
	cin >> n;
	int a, b;
	cin >> a >> b;
	vis[0] = 1;
	for(int i = 1, a, b, t; i < n; i++) {
		cin >> a >> b;
		string s;
		cin >> s;
		if(s[0] == 'p')
			t = 1;
		if(s[0] == 'c')
			t = 2;
		if(s[0] == 'm')
			t = 3;
		edge[a].push_back({b, t});
		cnt[a][t]++;
		edge[b].push_back({a, t});
		cnt[b][t]++;
	}
	dfs(a);
	if(dep[b] & 1) {
		memset(anc[0], 0, sizeof anc[0]);
		memset(pat, 0, sizeof pat);
		memset(dep, 0, sizeof dep);
		//cerr << "here\n";
		dfs(b);
		dfs(b, 1);
		go(a, 0);
		build(n);
		//for(int i = 1; i <= n; i++)
			//cout << lca(i, a) << " \n"[i == n];
		bool ok = 0;
		for(int i = 1; i <= n; i++)
			ok |= (pat[i] & 1) && lca(i, a) != b && !vis[anc[0][i]] && can[i] && (!vis[lca(i, a)] || dis(a, i) <= dep[i]);
		cout << (ok ? "Magenta" : "Marin") << '\n';
	}// Lost or draw
	else {
		memset(anc[0], 0, sizeof anc[0]);
		memset(pat, 0, sizeof pat);
		memset(dep, 0, sizeof dep);
		//cerr << "owo\n";
		dfs(a);
		dfs(a, 0);
		go(b, 1);
		build(n);
		bool ok = 0;
		for(int i = 1; i <= n; i++)
			ok |= (pat[i] & 2) && lca(i, b) != a && !vis[anc[0][i]] && can[i] && (!vis[lca(i, b)] || dis(b, i) < dep[i]);
		cout << (ok ? "Magenta" : "Paula") << '\n';
	}// Win or draw
}
/*
5
3 5
1 2 magenta
1 3 magenta
2 4 plava
2 5 crvena

5
1 4
2 1 plava
1 3 crvena
5 2 plava
4 1 magenta

*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:82:12: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |   cnt[b][t]++;
      |   ~~~~~~~~~^~

Subtask #1
0 / 30.0

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

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 16748 KB Output is correct
2 Correct 125 ms 16748 KB Output is correct
3 Correct 115 ms 16748 KB Output is correct
4 Correct 124 ms 16748 KB Output is correct
5 Correct 129 ms 16748 KB Output is correct
6 Correct 3 ms 3948 KB Output is correct
7 Correct 3 ms 3948 KB Output is correct
8 Correct 3 ms 3948 KB Output is correct

Subtask #3
0 / 50.0

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