Submission #491100

#	Time	Username	Problem	Language	Result	Execution time	Memory
491100		inksamurai	Magenta (COCI21_magenta)	C++17	30 / 110	68 ms	7948 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});
	}
	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);
	}
	vi pok(2,0);
	rep(t,2){
		rep(v,n){
			for(auto edge : adj[v]){
				int u=edge.fi;
				bool gok=1;
				if(dist[t][u]!=-1) gok=gok and dist[t][u]>dist[t^1][u];
				if(dist[t][v]!=-1) gok=gok and dist[t][v]>dist[t^1][v];
				if(dist[t][u]==-1 
					and dist[t][v]==-1 
					and max(dist[t^1][v],dist[t^1][u])!=-1
					and gok){
					pok[t]=1;
				}
				// if(t==0 and pok[t]){
				// 	cout<<dist[t][v]<<"\n";
				// 	cout<<u<<" "<<v<<"\n";
				// 	exit(0);
				// }
			}
		}
	}
	bool gok=0;
	for(auto edge : adj[_a]){
		if(edge.se!=1) gok=1;
	}
	if(gok==0){
		cout<<"Marin\n";
		exit(0);
	}
	if(dist[2][_b]%2==0){
		if(pok[0]){
			cout<<"Magenta\n";
		}else{
			cout<<"Paula\n";
		}
	}else{
		if(pok[1]){
			cout<<"Magenta\n";
		}else{
			cout<<"Marin\n";
		}
	}
//
	return 0;
}

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