oj.uz

Submission #858197

# Submission time Handle Problem Language Result Execution time Memory
858197 2023-10-07T14:58:46 Z serifefedartar Magenta (COCI21_magenta) C++17
30 / 110
 46 ms 6824 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18; 
const ll INF = 1e15;
const ll MAXN = 1e5 + 5;

int a, b;
vector<vector<pair<int,int>>> graph;
int d[MAXN];
int get_dist(int node, int parent, int dist) {
	if (node == b)
		return dist;
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		int q = get_dist(u.f, node, dist + 1);
		if (q != -1) 
			return q;
	}
	return -1;
}

void dfs(int node, int parent, int dist) {
	d[node] = dist;
	for (auto u : graph[node]) {
		if (u.f == parent || u.s == 2)
			continue;
		dfs(u.f, node, dist + 1);
	}
}


bool swapped = false, control = false;
void dfs2(int node, int parent, int dist, int q) {
	if (q == 2) {
		control = true;
		return ;
	}

	for (auto u : graph[node]) {
		if (u.s == 1 || u.f == parent)
			continue;

		if (d[u.f] == -1)
			dfs2(u.f, node, dist + 1, q + 1);
		else if (d[u.f] > dist + 1 + !swapped)
			dfs2(u.f, node, dist + 1, 0);
	}
}

int main() {
	fast
	memset(d, -1, sizeof(d));
	int n;
	cin >> n;

	cin >> a >> b;
	graph = vector<vector<pair<int,int>>>(n+1, vector<pair<int,int>>());
	for (int i = 1; i < n; i++) {
		int u, v;
		string type;
		cin >> u >> v >> type;
		int t;
		if (type == "magenta")
			t = 0;
		else if (type == "plava")
			t = 1;
		else
			t = 2;
		graph[u].push_back({v, t});
		graph[v].push_back({u, t});
	}

	bool check_a = false, check_b = false;
	for (auto u : graph[a]) {
		if (u.s != 2)
			check_a = true;
	}
	for (auto u : graph[b]) {
		if (u.s != 1)
			check_b = true;
	}

	if (!check_a) {
		cout << "Marin\n";
		return 0;
	}
	if (!check_b) {
		cout << "Paula\n";
		return 0;
	}


	int Q = get_dist(a, a, 0);

	if (Q % 2) {
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < graph[i].size(); j++) {
				if (graph[i][j].s != 0)
					graph[i][j].s = 3 - graph[i][j].s;
			}
		}
		swapped = true;
		swap(a, b);
	}
	dfs(a, a, 0);
	dfs2(b, b, 0, 0);

	if (control)
		cout << "Magenta\n";
	else {
		if (swapped)
			cout << "Marin\n";
		else
			cout << "Paula\n";		
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    for (int j = 0; j < graph[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 6824 KB Output is correct
2 Correct 35 ms 6736 KB Output is correct
3 Correct 36 ms 6748 KB Output is correct
4 Correct 40 ms 6736 KB Output is correct
5 Correct 46 ms 6736 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -