Submission #406360

#	Time	Username	Problem	Language	Result	Execution time	Memory
406360		EncryptingWolf	Toy Train (IOI17_train)	C++14	38 / 100	2092 ms	2940 KiB

train

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <tuple>
typedef long long ll;
#define FOR(i,x,y) for(ll i = x; i < y; i++)
using namespace std;

vector<int> players;
vector<set<ll>> adj;
vector<ll> inCounts;
set<ll> badNodesF;
set<ll> batteries;
set<ll> nodesLeft;

void dfs(ll node, bool playerWants, set<ll>& badNodes, vector<ll>& visited, bool losing)
{
	if (badNodesF.count(node))
		return;
	visited[node]++;
	if (players[node] == playerWants)
	{
		if (visited[node] != 1)
			return;
		else
		{
			badNodes.emplace(node);
		}
	}
	else
	{
		if (losing&&visited[node] <= inCounts[node])
		{
			visited[node] = inCounts[node] + 2; badNodes.emplace(node);
		}
		else {
			if (visited[node] != inCounts[node])
			{
				return;
			}
			else
			{

				badNodes.emplace(node);
			}
		}
	}

	for (auto i : adj[node])
	{
		dfs(i, playerWants, badNodes, visited, false);
	}
}


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

	adj.resize(n);
	FOR(i, 0, u.size())
	{
		adj[v[i]].emplace(u[i]);
		inCounts[u[i]] += 1;

	}
	FOR(i, 0, n)
	{
		if (r[i])
			batteries.emplace(i);
		nodesLeft.emplace(i);
	}
	while (true)
	{
		vector<ll> visited(n);
		set<ll> badNodes;
		for (auto i : batteries)
		{

				badNodes.emplace(i);
				dfs(i, true, badNodes, visited, true);
		}

		set<ll> badNodes2;
		vector<ll> visited2(n);

		for (auto i : nodesLeft)
		{
			if (badNodes.count(i) == 0 && badNodesF.count(i)==0)
			{
				badNodes2.emplace(i);
				dfs(i, false, badNodes2, visited2, true);
			}
		}

		for (auto i : badNodes2)
		{
//			if (badNodes2.count(i))
	//		{
				r[i] = 0;
				batteries.erase(i);
		//	}
		}
		if (badNodes2.size()==0)
			break;

		
		/*for (auto i : badNodes2)
			cout << i;*/
		//cout << endl;
		//badNodesF = badNodes2;

		for (auto j : nodesLeft)
		{
			auto& i = adj[j];
			for (auto j : badNodes2)
			{
				i.erase(j);
			}
			
		}
		for (auto i : badNodes2)
		{
			nodesLeft.erase(i);
			badNodesF.emplace(i);
			for (auto j : adj[i])
				inCounts[j]--;
		}

	}

	// !badNodes is B
	// Badnodes2 are B
	// Neither is B
	vector<int> re;
	FOR(i, 0, n)
	{
		if (badNodesF.count(i))
			re.push_back(0);
		else
			re.push_back(1);
	}
	return re;
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:8:36: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i,x,y) for(ll i = x; i < y; i++)
......
   65 |  FOR(i, 0, u.size())
      |      ~~~~~~~~~~~~~~                 
train.cpp:65:2: note: in expansion of macro 'FOR'
   65 |  FOR(i, 0, u.size())
      |  ^~~

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