Submission #136590

#	Time	Username	Problem	Language	Result	Execution time	Memory
136590		Lawliet	장난감 기차 (IOI17_train)	C++14	11 / 100	14 ms	2168 KiB

train

#include <bits/stdc++.h>

#define MAX 5010

using namespace std;

int N, M;
int curComponent;

int node[MAX];

bool marc[MAX][2];
bool isCycle[MAX];
bool isSpecial[MAX];
bool hasRecharge[MAX];

vector<int> order;

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

void DFS(int i, int type, int& sz)
{
	marc[i][type] = true;

	sz++;

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

		//printf("i = %d prox = %d    %d\n",i,prox,marc[prox][type]);

		if(marc[prox][type]) continue;

		if(type == 1) 
		{
			node[prox] = node[i];

			if( isSpecial[prox] ) hasRecharge[ node[i] ] = true;
		}

		DFS(prox , type , sz);
	}

	if(type == 0) order.push_back( i );
}

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] + 1 ][0].push_back( v[g] + 1 );
		grafo[ v[g] + 1 ][1].push_back( u[g] + 1 );

		if(u[g] == v[g]) isCycle[ u[g] + 1 ] = true; 

		//printf("OIII %d %d\n",u[g] + 1,v[g] + 1);
	}

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

	int t = 0;

	for(int g = 1 ; g <= N ; g++)
		if(!marc[g][0]) DFS(g , 0 , t);

	while(!order.empty())
	{
		int cur = order.back();
		order.pop_back();

		if(marc[cur][1]) continue;

		node[cur] = ++curComponent;

		if(isCycle[cur] && isSpecial[cur])
			hasRecharge[ node[cur] ] = true;

		//printf("cuuur = %d\n",cur);
		int size = 0;

		DFS(cur , 1 , size);

		if( isSpecial[cur] && size > 1 ) hasRecharge[ node[cur] ] = true;

		//printf("cur = %d    %d\n",cur,hasRecharge[node[cur]]);
	}

	for(int g = 0 ; g < M ; g++)
	{
		int i = u[g] + 1;
		int j = v[g] + 1;

		i = node[i]; j = node[j];

		if(i == j) continue;

		SCC[j].push_back( i );
	}

	for(int g = curComponent ; g > 0 ; g--)
	{
		if(!hasRecharge[g]) continue;

		for(int h = 0 ; h < SCC[g].size() ; h++)
			hasRecharge[ SCC[g][h] ] = true;
	}

	vector<int> ans;

	for(int g = 1 ; g <= N ; g++)
	{
		int i = node[g];

		if(hasRecharge[i]) 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(3);

	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 DFS(int, int, int&)':
train.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i][type].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:112:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0 ; h < SCC[g].size() ; h++)
                   ~~^~~~~~~~~~~~~~~

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