oj.uz

Submission #506215

# Submission time Handle Problem Language Result Execution time Memory
506215 2022-01-11T21:50:41 Z Hanksburger Toy Train (IOI17_train) C++17
27 / 100
 358 ms 1616 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 716 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 756 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1412 KB Output is correct
2 Correct 25 ms 1356 KB Output is correct
3 Correct 46 ms 1360 KB Output is correct
4 Correct 95 ms 1348 KB Output is correct
5 Correct 20 ms 1352 KB Output is correct
6 Correct 64 ms 1348 KB Output is correct
7 Correct 40 ms 1356 KB Output is correct
8 Correct 9 ms 1368 KB Output is correct
9 Correct 6 ms 1300 KB Output is correct
10 Correct 8 ms 1356 KB Output is correct
11 Correct 6 ms 1356 KB Output is correct
12 Correct 6 ms 1228 KB Output is correct
13 Correct 8 ms 1356 KB Output is correct
14 Correct 7 ms 1412 KB Output is correct
15 Correct 7 ms 1356 KB Output is correct
16 Correct 7 ms 1404 KB Output is correct
17 Correct 6 ms 1356 KB Output is correct
18 Correct 117 ms 1068 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1228 KB Output is correct
2 Correct 123 ms 1412 KB Output is correct
3 Correct 193 ms 1528 KB Output is correct
4 Correct 27 ms 1604 KB Output is correct
5 Correct 358 ms 1532 KB Output is correct
6 Correct 275 ms 1560 KB Output is correct
7 Correct 265 ms 1552 KB Output is correct
8 Correct 137 ms 1484 KB Output is correct
9 Correct 6 ms 1452 KB Output is correct
10 Correct 7 ms 1612 KB Output is correct
11 Correct 7 ms 1612 KB Output is correct
12 Correct 8 ms 1616 KB Output is correct
13 Correct 219 ms 1548 KB Output is correct
14 Correct 197 ms 1404 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 844 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 716 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 756 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Incorrect 1 ms 460 KB WA in grader: Wrong returned array size
13 Halted 0 ms 0 KB -