Submission #858206

#	Time	Username	Problem	Language	Result	Execution time	Memory
858206		serifefedartar	Magenta (COCI21_magenta)	C++17	110 / 110	44 ms	8540 KiB

Main

#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 && u.f != b)
			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 (stderr)

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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50