Submission #136579

#	Time	Username	Problem	Language	Result	Execution time	Memory
136579		Lawliet	Toy Train (IOI17_train)	C++14	0 / 100	12 ms	1528 KiB

train

#include <bits/stdc++.h>

#define MAX 5010

using namespace std;

int N, M;
int curComponent;

int node[MAX];
int indegree[MAX];

bool win[MAX];
bool marc[MAX];
bool isCycle[MAX];
bool isSpecial[MAX];
bool ArezouOwn[MAX];
bool BorzouOwn[MAX];

queue<int> q;

vector<int> grafo[MAX][2];

void add(int i)
{
	q.push( i );
	marc[i] = true;
}

void TopologicalSorting()
{
	for(int g = 1 ; g <= N ; g++)
		if(indegree[g] == 0) add( g );

	while(!q.empty())
	{
		int cur = q.front(); q.pop();
		//printf("cur %d\n",cur);

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

			//printf("cur = %d    prox = %d     %d\n",cur,prox,indegree[prox]);

			indegree[ prox ]--;

			if(indegree[prox] == 0)
				add( prox );
		}
	}
}

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++)
	{
		u[g]++; v[g]++;

		indegree[ v[g] ]++;

		grafo[ u[g] ][0].push_back( v[g] );
		grafo[ v[g] ][1].push_back( u[g] );
	}

	for(int g = 0 ; g < r.size() ; g++)
		isSpecial[ r[g] + 1 ] = true; 

	TopologicalSorting();

	for(int g = 1 ; g <= N ; g++)
		if(!marc[g] && isSpecial[g])
			add( g ), win[g] = true;

	memset(marc , false , sizeof(marc));

	while(!q.empty())
	{
		int cur = q.front(); q.pop();

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

			if(!marc[prox])
				add( prox ), win[prox] = true;
		}
	}

	vector<int> ans;

	for(int g = 1 ; g <= N ; g++)
	{
		if(win[g]) 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 < nn ; g++)
		v1.push_back( 1 );

	v2.push_back(2);
	//v2.push_back(3);
	v2.push_back(8);

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

		n1--;n2--;

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

	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 'void TopologicalSorting()':
train.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int g = 0 ; g < grafo[cur][0].size() ; g++)
                   ~~^~~~~~~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < r.size() ; g++)
                  ~~^~~~~~~~~~
train.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int g = 0 ; g < grafo[cur][1].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