Submission #406378

#	Time	Username	Problem	Language	Result	Execution time	Memory
406378		EncryptingWolf	장난감 기차 (IOI17_train)	C++14	49 / 100	2079 ms	3148 KiB

train

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

vector<int> players;
vector<unordered_set<int>> adj;
vector<int> inCounts;

unordered_set<int> badNodesF;
unordered_set<int> batteries;
unordered_set<int> nodesLeft;
#include <stack>

void dfs(bool playerWants, unordered_set<int>& badNodes, vector<int>& visited, vector<int>& starts)
{
	vector<pair<int,int>> s;
	s.reserve(starts.size());
	for (auto i : starts)
		s.push_back({ i,true });
	while (s.size())
	{
		int node = s[s.size() - 1].first;
		bool losing = s[s.size() - 1].second;
		s.pop_back();
		/*if (badNodesF.count(node))
			continue;*/

		visited[node]++;
		if (players[node] == playerWants)
		{
			if (visited[node] != 1)
				continue;
			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])
				{
					continue;
				}
				else
				{

					badNodes.emplace(node);
				}
			}
		}

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


vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
	int 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);
	}
	vector<int> visited2(n);
	vector<int> visited(n);

	while (true)
	{
		for (auto i : nodesLeft)
		{
			visited[i] = 0;
			visited2[i] = 0;
		}
		unordered_set<int> badNodes;

		vector<int> s;
		for (auto i : batteries)
		{

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

		unordered_set<int> badNodes2;

		vector<int> k;
		for (auto i : nodesLeft)
		{
			if (badNodes.count(i) == 0 && badNodesF.count(i) == 0)
			{
				badNodes2.emplace(i);
				k.push_back(i);
			}
		}

		dfs(false, badNodes2, visited2, k);
		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:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i,x,y) for(int i = x; i < y; i++)
......
   79 |  FOR(i, 0, u.size())
      |      ~~~~~~~~~~~~~~                  
train.cpp:79:2: note: in expansion of macro 'FOR'
   79 |  FOR(i, 0, u.size())
      |  ^~~

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