Submission #136587

#	Time	Username	Problem	Language	Result	Execution time	Memory
136587		Lawliet	Toy Train (IOI17_train)	C++14	0 / 100	16 ms	6904 KiB

train

#include <bits/stdc++.h>

#define MAX 20
#define EXP 1024*32 + 10

using namespace std;

int N, M;

int dp[MAX][EXP];//1 se A ganha

bool AOwn[MAX];
bool isSpecial[MAX];

vector<int> grafo[MAX];

vector<int> s;

int test(int i)
{
	int ind = s.size() - 1;

	bool flag = false;

	while(ind > 0 && s[ind] != i)
	{
		flag = flag || isSpecial[ s[ind] ];

		ind--;
	}

	flag = flag || isSpecial[ i ];

	if(flag) return 1;
	return 0;
}

int DP(int i, int mask)
{
	if(dp[i][mask] != -1) return dp[i][mask];

	s.push_back( i );

	int mx = 0;
	int mn = 1;

	//printf("oi  %d %d\n",i,mask);

	for(int g = 0 ; g < grafo[i].size() ; g++)
	{
		int cur = grafo[i][g];

		//printf("cur = %d\n",cur);

		if(mask & (1 << cur))//ENTREI CICLO
		{
			int aux = test(cur);

			mx = max(mx , aux);
			mn = min(mn , aux);
		}
		else
		{
			int aux = DP(cur , mask + (1 << cur));

			mx = max(mx , aux);
			mn = min(mn , aux);
		} 

		//printf("sai\n");
	}

	if(AOwn) dp[i][mask] = mx;
	else dp[i][mask] = mn;

	//printf("i = %d  m = %d  %d\n",i,mask,dp[i][mask]);

	s.pop_back();

	return dp[i][mask];
}

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

	for(int g = 0 ; g < M ; g++)
		grafo[ u[g] ].push_back( v[g] );

	for(int g = 0 ; g < N ; g++)
	{
		if(r[g] == 1) isSpecial[g] = true;
		else isSpecial[g] = false;
	}

	for(int g = 0 ; g < N ; g++)
	{
		if(a[g] == 1) AOwn[g] = true;
		else AOwn[g] = false;
	}

	memset(dp , -1 , sizeof(dp));

	vector<int> ans;

	for(int g = 0 ; g < N ; g++)
	{
		if(DP(g , (1 << g)) == 1) ans.push_back(1);
		else ans.push_back(0);
	}

	return ans;
}

/*int main()
{
	int nn, mm, n1, n2;
	scanf("%d %d",&nn,&mm);

	vector<int> v1, v2;
	vector<int> uu, vv;

	for(int g = 0 ; g < mm ; g++)
	{
		scanf("%d %d",&n1,&n2);

		uu.push_back( n1 ); 
		vv.push_back( n2 );
	}

	for(int g = 0 ; g < nn ; g++)
	{
		scanf("%d",&n1);

		v1.push_back(n1);
	}

	for(int g = 0 ; g < nn ; g++)//ESPECIAL
	{
		scanf("%d",&n1);

		v2.push_back(n1);
	}

	vector<int> ans = who_wins(v1 , v2 , uu , vv);

	for(int g = 0 ; g < nn ; g++)
		printf("%d ",ans[g]);
}*/

Compilation message (stderr)

train.cpp: In function 'int DP(int, int)':
train.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~

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