Submission #491106

#	Time	Username	Problem	Language	Result	Execution time	Memory
491106		inksamurai	Magenta (COCI21_magenta)	C++17	110 / 110	63 ms	9740 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3cSpNGp ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;

int main(){
_3cSpNGp;
	int n;
	cin>>n;
	int _a,_b;
	cin>>_a>>_b;
	_a--,_b--;
	vec(vec(pii)) adj(n);
	rep(i,n-1){
		int u,v;
		string s;
		cin>>u>>v>>s;
		u--,v--;
		adj[u].pb({v,s=="magenta"?2:s=="crvena"?1:0});
		adj[v].pb({u,s=="magenta"?2:s=="crvena"?1:0});
	}
	bool poka=0,pokb=0;
	for(auto edge : adj[_a]){
		int u=edge.fi,color=edge.se;
		if(u!=_b and color!=1) poka=1;
	}
	for(auto edge : adj[_b]){
		int u=edge.fi,color=edge.se;
		if(color!=0) pokb=1;
	}
	if(!poka){
		cout<<"Marin\n";
		exit(0);
	}
	if(!pokb){
		cout<<"Paula\n";
		exit(0);
	}
	vec(vi) dist(3,vi(n,-1));
	rep(t,3){
		auto dfs=[&](auto self,int v,int par)->void{
			for(auto edge : adj[v]){
				int u=edge.fi,color=edge.se;
				if(u==par) continue;
				if(t==0 and color==1) continue;
				if(t==1 and color==0) continue;
				dist[t][u]=dist[t][v]+1;
				self(self,u,v); 
			}
		};
		int root=_a;
		if(t==1) root=_b;
		dist[t][root]=0;
		dfs(dfs,root,-1);
	}
	bool cand=0;
	auto magicaldfs=[&](auto self,int v,int t,int par)->void{
		for(auto edge : adj[v]){
			int u=edge.fi,color=edge.se;
			if(u==par or dist[t^1][u]==-1) continue;
			if(dist[t][u]!=-1 and dist[t][u]<=dist[t^1][u]) continue;
			if(dist[t][u]==-1 and dist[t][v]==-1){
				cand=1;
			}
			self(self,u,t,v);
		}
	};
	magicaldfs(magicaldfs,(dist[2][_b]%2==0?_b:_a),(dist[2][_b]%2),-1);
	if(dist[2][_b]%2==0){
		if(cand==1){
			cout<<"Magenta\n";
		}else{
			cout<<"Paula\n";
		}
	}else{
		if(cand==1){
			cout<<"Magenta\n";
		}else{
			cout<<"Marin\n";
		}
	}
//
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:7: warning: unused variable 'u' [-Wunused-variable]
   40 |   int u=edge.fi,color=edge.se;
      |       ^
Main.cpp: In instantiation of 'main()::<lambda(auto:24, int, int, int)> [with auto:24 = main()::<lambda(auto:24, int, int, int)>]':
Main.cpp:80:67:   required from here
Main.cpp:71:18: warning: unused variable 'color' [-Wunused-variable]
   71 |    int u=edge.fi,color=edge.se;
      |                  ^~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50