oj.uz

Submission #447839

# Submission time Handle Problem Language Result Execution time Memory
447839 2021-07-27T17:06:44 Z Jasiekstrz Magenta (COCI21_magenta) C++17
30 / 110
 307 ms 32980 KB 
#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=="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;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Incorrect 5 ms 7364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 32412 KB Output is correct
2 Correct 130 ms 26028 KB Output is correct
3 Correct 239 ms 32980 KB Output is correct
4 Correct 116 ms 23072 KB Output is correct
5 Correct 109 ms 23700 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 5 ms 7244 KB Output is correct
8 Correct 4 ms 7244 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Incorrect 5 ms 7364 KB Output isn't correct
4 Halted 0 ms 0 KB -