Submission #1276394

#TimeUsernameProblemLanguageResultExecution timeMemory
1276394warrennMagenta (COCI21_magenta)C++20
30 / 110
94 ms9464 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=1e5; int dist[maxn+2][2]; vector<pair<int,int> >adj[maxn+2]; void dfs(int cur,int par){ for(auto x : adj[cur]){ if(x.first==par || x.second==1)continue; dist[x.first][0]=dist[cur][0]+1; dfs(x.first,cur); } } void dfs2(int cur,int par){ for(auto x : adj[cur]){ // cout<<cur<<" "<<x.second<<endl; // cout<<x.first<<endl; if(x.first==par || x.second==0)continue; dist[x.first][1]=dist[cur][1]+1; dfs2(x.first,cur); } } int siapa=0; bool oke=false; void solve(int cur,int par){ for(auto x : adj[cur]){ if(x.first==par || (dist[x.first][siapa]!=-1 && dist[x.first][siapa]<=dist[x.first][1-siapa]))continue; if(x.second==siapa)continue; // cout<<siapa<<" "<<cur<<endl; solve(x.first,cur); if(dist[x.first][siapa]==-1 && dist[cur][siapa]==-1){ oke=true; } } } signed main(){ memset(dist,-1,sizeof dist); int n; cin>>n; int a,b; cin>>a>>b; for(int q=1;q<n;q++){ int u,v; cin>>u>>v; string s; cin>>s; int col=0; if(s=="crvena"){ col=1; } else if(s=="magenta"){ col=2; } adj[u].push_back({v,col}); adj[v].push_back({u,col}); } dist[a][0]=dist[b][1]=0; dfs(a,-1); dfs2(b,-1); if(dist[a][1]==-1 && dist[b][0]==-1){ cout<<"Magenta"<<endl; return 0; } if(dist[b][0]!=-1 && dist[b][0]%2==1){ siapa=1; } if(siapa==0){ solve(a,-1); if(oke){ cout<<"Magenta"<<endl; } else{ cout<<"Paula"<<endl; } } else{ solve(b,-1); if(oke){ cout<<"Magenta"<<endl; } else{ cout<<"Marin"<<endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...