Submission #506214

#	Time	Username	Problem	Language	Result	Execution time	Memory
506214		Hanksburger	Toy Train (IOI17_train)	C++17	16 / 100	127 ms	1416 KiB

train

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[5005], revadj[5005], vec, ans;
bool visited[5005], bo[5005], ol[5005];
queue<int> q;
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
	int n=a.size(), m=u.size();
	bool subtask1=1, subtask3=1, subtask4=1;
	for (int i=0; i<n; i++)
	{
		if (a[i])
			subtask4=0;
		else
			subtask3=0;
	}
	for (int i=0; i<m; i++)
	{
		if (v[i]!=u[i] && v[i]!=u[i]+1)
		{
			subtask1=0;
			break;
		}
	}
	if (subtask1)
	{
		for (int i=0; i<m; i++)
		{
			if (v[i]==u[i])
				bo[u[i]]=1;
			else if (v[i]==u[i]+1)
				ol[u[i]]=1;
		}
		for (int i=0; i<n; i++)
		{
			for (int j=i; j<n; j++)
			{
				if (bo[j] && a[j] && r[j])
				{
					ans.push_back(1);
					break;
				}
				else if (bo[j] && !a[j] && !r[j])
				{
					ans.push_back(0);
					break;
				}
				else if (!ol[j])
				{
					ans.push_back(r[j]);
					break;
				}
			}
		}
	}
	else if (subtask3)
	{
		for (int i=0; i<m; i++)
		{
			adj[u[i]].push_back(v[i]);
			revadj[v[i]].push_back(u[i]);
		}
		for (int i=0; i<n; i++)
		{
			if (!r[i])
				continue;
			for (int j=0; j<n; j++)
				visited[j]=0;
			visited[i]=1;
			q.push(i);
			bool ok=0;
			while (!q.empty())
			{
				int u=q.front();
				q.pop();
				for (int j=0; j<adj[u].size(); j++)
				{
					int v=adj[u][j];
					if (v==i)
					{
						ok=1;
						break;
					}
					if (!visited[v])
					{
						visited[v]=1;
						q.push(v);
					}
				}
				if (ok)
					while (!q.empty())
						q.pop();
			}
			if (ok)
				vec.push_back(i);
		}
		for (int i=0; i<n; i++)
			visited[i]=0;
		for (int i=0; i<vec.size(); i++)
		{
			int u=vec[i];
			visited[u]=1;
			q.push(u);
		}
		while (!q.empty())
		{
			int u=q.front();
			q.pop();
			for (int i=0; i<revadj[u].size(); i++)
			{
				int v=revadj[u][i];
				if (!visited[v])
				{
					visited[v]=1;
					q.push(v);
				}
			}
		}
		for (int i=0; i<n; i++)
			ans.push_back(visited[i]);
	}
	else if (subtask4)
	{
		for (int i=0; i<m; i++)
		{
			adj[u[i]].push_back(v[i]);
			revadj[v[i]].push_back(u[i]);
		}
		for (int i=0; i<n; i++)
		{
			if (r[i])
				continue;
			for (int j=0; j<n; j++)
				visited[j]=0;
			visited[i]=1;
			q.push(i);
			bool ok=0;
			while (!q.empty())
			{
				int u=q.front();
				q.pop();
				for (int j=0; j<adj[u].size(); j++)
				{
					int v=adj[u][j];
					if (r[v])
						continue;
					if (v==i)
					{
						ok=1;
						break;
					}
					if (!visited[v])
					{
						visited[v]=1;
						q.push(v);
					}
				}
				if (ok)
					while (!q.empty())
						q.pop();
			}
			if (ok)
				vec.push_back(i);
		}
		for (int i=0; i<n; i++)
			visited[i]=0;
		for (int i=0; i<vec.size(); i++)
		{
			int u=vec[i];
			visited[u]=1;
			q.push(u);
		}
		while (!q.empty())
		{
			int u=q.front();
			q.pop();
			for (int i=0; i<revadj[u].size(); i++)
			{
				int v=revadj[u][i];
				if (!visited[v])
				{
					visited[v]=1;
					q.push(v);
				}
			}
		}
		for (int i=0; i<n; i++)
			ans.push_back(visited[i]);
	}
	return ans;
}

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:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int j=0; j<adj[u].size(); j++)
      |                   ~^~~~~~~~~~~~~~
train.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (int i=0; i<vec.size(); i++)
      |                 ~^~~~~~~~~~~
train.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |    for (int i=0; i<revadj[u].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~
train.cpp:142:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int j=0; j<adj[u].size(); j++)
      |                   ~^~~~~~~~~~~~~~
train.cpp:167:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |   for (int i=0; i<vec.size(); i++)
      |                 ~^~~~~~~~~~~
train.cpp:177:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |    for (int i=0; i<revadj[u].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~

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