Submission #137223

#	Time	Username	Problem	Language	Result	Execution time	Memory
137223		Mahdi_Jfri	Toy Train (IOI17_train)	C++14	15 / 100	2050 ms	4088 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] , out[maxn] , in[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)
{
	for(auto u : adj[v])
	{
		int w;
		if(u == v)
			w = is[v];
		else
			w = DFS(u);

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

	return !who[v];
}

bool visited[maxn] , has[maxn] , wtf[maxn];
vector<int> topol , ver[maxn];
int C , color[maxn];

void dfs(int v)
{
	visited[v] = 1;
	for(auto u : out[v])
		if(!visited[u])
			dfs(u);

	topol.pb(v);
}

void sfd(int v)
{
	visited[v] = 1;
	color[v] = C;
	ver[C].pb(v);
	has[color[v]] |= is[v];
	for(auto u : in[v])
		if(!visited[u])
			sfd(u);
}

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++)
	{
		is[i] = r[i] , who[i] = a[i];
		all &= who[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]);
		out[u[i]].pb(v[i]);
		in[v[i]].pb(u[i]);

		if(v[i] == u[i])
			wtf[i] = 1;
	}

	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)
	{
		for(int i = 0; i < n; i++)
			if(!visited[i])
				dfs(i);

		reverse(topol.begin() , topol.end());
		memset(visited , 0 , sizeof visited);

		for(auto v : topol)
			if(!visited[v])
			{
				sfd(v);
				if((int)ver[C].size() == 1)
					has[C] &= wtf[ver[C][0]];
				C++;
			}

		for(int i = C - 1; i >= 0; i--)
			for(auto v : ver[i])
				for(auto u : out[v])
					has[i] |= has[color[u]];

		for(int i = 0; i < n; i++)
			ans.pb(has[color[i]]);
      while(1);
	}
	else
	{
		for(int i = 0; i < n; i++)
			if(!visited[i] && !is[i])
				dfs(i);
		
		reverse(topol.begin() , topol.end());
		memset(visited , 0 , sizeof visited);

		for(auto v : topol)
			if(!visited[v])
			{
				sfd(v);
				has[C] = (ver[C].size() > 1) || (wtf[ver[C][0]]);
				C++;
			}

		for(int i = C - 1; i >= 0; i--)
			for(auto v : ver[i])
				for(auto u : out[v])
					has[i] |= has[color[u]];

		for(int i = 0; i < n; i++)
		{
			if(!is[i])
				is[i] = has[color[i]];
			else
				is[i] = 0;
		}
	}

	return ans;
}

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