Submission #447840

#	Time	Username	Problem	Language	Result	Execution time	Memory
447840		Jasiekstrz	Magenta (COCI21_magenta)	C++17	110 / 110	245 ms	32428 KiB

Main

#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;
				auto old=nxt[x[1-t]][1-t];
				nxt[x[1-t]][1-t]={x[t],nxt[x[t]][t].se};
				improve(solve(y,1-t));
				nxt[x[1-t]][1-t]=old;
			}
		}
	}

	//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=="crvena")
			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;
}

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