Submission #137204

#	Time	Username	Problem	Language	Result	Execution time	Memory
137204		Mahdi_Jfri	Toy Train (IOI17_train)	C++14	10 / 100	9 ms	1272 KiB

train

#include "train.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)

const int maxn = 5e3 + 20;

map<pair<pair<int , int> , int> , bool> mp;

int n , who[maxn];
bool is[maxn];

vector<int> adj[maxn];

int get_dp(int mask1 , int mask2 , int v)
{
	pair<pair<int , int> , int> tmp = {{mask1 , mask2} , v};
	if(mp.count(tmp))
		return mp[tmp];

	for(auto u : adj[v])
	{
		int w;
		if(bit(mask1 , u))
			w = 1;
		else if(bit(mask2 , u))
			w = 0;
		else
		{
			if(is[u])
				w = get_dp(mask1 | mask2 | (1 << u) , 0 , u);
			else
				w = get_dp(mask1 , mask2 | (1 << u) , u);
		}

		if(w == who[v])
		{
			mp[tmp] = who[v];
			return who[v];
		}
	}

	mp[tmp] = 1 - who[v];
	return 1 - who[v];
}

int DFS(int v)
{
	sort(adj[v].begin() , adj[v].end());
	if((int)adj[v].size() > 1 && DFS(adj[v][1]) == who[v])
		return who[v];

	if(adj[v][0] == v && is[v] == who[v])
		return who[v];

	return !who[v];
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
	n = a.size();

	bool all = 1;
	for(int i = 0; i < n; i++)
	{
		all &= who[i];
		is[i] = r[i] , who[i] = a[i];
	}

	bool f = 1;
	for(int i = 0; i < (int)u.size(); i++)
	{
		f &= (v[i] - u[i] <= 1) && (v[i] >= u[i]);
		adj[u[i]].pb(v[i]);
	}

	vector<int> ans;
	if(n <= 15)
	{
		for(int i = 0; i < n; i++)
		{
			if(is[i])
				ans.pb(get_dp(1 << i , 0 , i));
			else
				ans.pb(get_dp(0 , (1 << i) , i));
		}
	}
	else if(f)
	{
		for(int i = 0; i < n; i++)
			ans.pb(DFS(i));
	}
	else if(all)
	{
	}
	else
	{
	}

	return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51