Submission #366333

#	Time	Username	Problem	Language	Result	Execution time	Memory
366333		kshitij_sodani	Magenta (COCI21_magenta)	C++14	110 / 110	175 ms	18028 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

int n;
vector<int> adj[100001];
vector<int> adj2[100001];
vector<int> adj3[100001];

int dist[100001];
int dist2[100001];

int cc,dd;
int st=0;
//llo pp=0;
void dfs(int no,int par=-1,int levv=0){
	if(no==dd){
/*		if(levv==1){
			pp=1;
		}*/
		if(levv%2==0){
			//cout<<"Paula"<<endl;
		}
		else{
			st=1;
			//cout<<"Marin"<<endl;
		}
	}
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no,levv+1);
		}
	}
}
void dfs2(int no,int par=-1,int levv=0){
	dist[no]=levv;
	for(auto j:adj2[no]){
		if(j!=par){
			dfs2(j,no,levv+1);
		}
	}
}
void dfs3(int no,int par=-1,int levv=0){
	dist2[no]=levv;
	for(auto j:adj3[no]){
		if(j!=par){
			dfs3(j,no,levv+1);
		}
	}
}
int ans=1;
void dfs4(int no,int par=-1,int levv=0){
	for(auto j:adj2[no]){
		if(j!=par){
			if(dist2[no]==-1 and dist2[j]==-1){
				ans=0;
			}
			if(dist2[j]==-1 or dist2[j]>=dist[j]){
				dfs4(j,no,levv+1);
			}
		}
	}
}

void dfs5(int no,int par=-1,int levv=0){
	for(auto j:adj3[no]){
		if(j!=par){
			if(dist[no]==-1 and dist[j]==-1){
				ans=0;
			}
			if(dist[j]==-1 or dist[j]>dist2[j]){
				dfs5(j,no,levv+1);
			}
		}
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	
	cin>>cc>>dd;
	cc--;
	dd--;
	for(int i=0;i<n-1;i++){
		int aa,bb;
		cin>>aa>>bb;
		string ee;
		cin>>ee;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
		if(ee=="plava" or ee=="magenta"){
			adj2[aa].pb(bb);
			adj2[bb].pb(aa);
		}
		if(ee=="crvena" or ee=="magenta"){
			adj3[aa].pb(bb);
			adj3[bb].pb(aa);
		}
	}
	if(true){
		if(adj2[cc].size()==0){
			cout<<"Marin"<<endl;
			return 0;
		}
		if(adj2[cc].size()==1){
			if(adj2[cc][0]==dd){
				cout<<"Marin"<<endl;
				return 0;
			}
		}
	}
	if(true){
		if(adj3[dd].size()==0){
			cout<<"Paula"<<endl;
			return 0;
		}
	}



	dfs(cc);
	for(int i=0;i<n;i++){
		dist[i]=-1;
		dist2[i]=-1;
	}
	dfs2(cc);
	dfs3(dd);
/*	for(int i=0;i<n;i++){
		cout<<dist[i]<<":"<<dist2[i]<<endl;
	}*/
	if(st==0){
		dfs5(dd);
		if(ans==0){
			cout<<"Magenta"<<endl;
		}
		else{
			cout<<"Paula"<<endl;
		}
	}
	else{
		dfs4(cc);
		if(ans==0){
			cout<<"Magenta"<<endl;
		}
		else{
			cout<<"Marin"<<endl;
		}
	}








 
	return 0;
}

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