#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
vector<pair<int,int>> e[N+10];
vector<pair<int,int>> eok[N+10][2];
pair<int,int> nxt[N+10][2];
map<pair<int,int>,int> dp;
set<pair<int,int>> stck;
void dfs_path(int x,int p,int pc,int t)
{
nxt[x][t]={p,pc};
for(auto [v,c]:e[x])
{
if(v!=p)
dfs_path(v,x,c,t);
}
return;
}
int solve(int x[2],int t)
{
if(dp.find({x[0],x[1]})!=dp.end())
return dp[make_pair(x[0],x[1])];
if(stck.find({x[0],x[1]})!=stck.end())
return 2;
stck.insert({x[0],x[1]});
int w=1-t;
auto improve=[&w,&t](int c)
{
if(c==t)
w=c;
else if(c==2 && w!=t)
w=c;
return;
};
if(nxt[x[t]][t].se!=1-t && nxt[x[t]][t].fi!=x[1-t])
{
int y[2]={x[0],x[1]};
y[t]=nxt[x[t]][t].fi;
w=solve(y,1-t);
}
else if(nxt[x[t]][t].fi!=x[1-t])
{
int ee=-1;
for(auto [v,c]:eok[x[t]][t])
{
if(c!=1-t && v!=x[1-t])
{
ee=v;
break;
}
}
if(ee==-1)
w=1-t;
else
{
int y[2]={x[0],x[1]};
y[t]=ee;
w=solve(y,1-t);
}
}
else
{
for(auto [v,c]:eok[x[t]][t])
{
if(c!=1-t && v!=x[1-t])
{
int y[2]={x[0],x[1]};
y[t]=v;
improve(solve(y,1-t));
}
}
}
//cerr<<x[0]<<" "<<x[1]<<" "<<t<<": "<<w<<"\n";
dp[make_pair(x[0],x[1])]=w;
stck.erase({x[0],x[1]});
return w;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
int start[2];
cin>>n;
cin>>start[0]>>start[1];
for(int i=1;i<n;i++)
{
int a,b;
string c;
cin>>a>>b>>c;
int cc;
if(c=="plava")
cc=0;
else if(c=="crevna")
cc=1;
else
cc=2;
e[a].emplace_back(b,cc);
e[b].emplace_back(a,cc);
}
for(int i=1;i<=n;i++)
{
for(int j:{0,1})
{
for(auto [v,c]:e[i])
{
if(c!=1-j)
eok[i][j].emplace_back(v,c);
}
}
}
dfs_path(start[0],0,0,1);
dfs_path(start[1],0,1,0);
int ans=solve(start,0);
if(ans==0)
cout<<"Paula\n";
else if(ans==1)
cout<<"Marin\n";
else
cout<<"Magenta\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7368 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
7244 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
22072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7368 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
7244 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
