oj.uz

Submission #506212

# Submission time Handle Problem Language Result Execution time Memory
506212 2022-01-11T21:47:09 Z Hanksburger Toy Train (IOI17_train) C++17
16 / 100
 123 ms 1612 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]);
	}
	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:9:31: warning: variable 'subtask4' set but not used [-Wunused-but-set-variable]
    9 |  bool subtask1=1, subtask3=1, subtask4=1;
      |                               ^~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 4 ms 752 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 748 KB Output is correct
8 Correct 4 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 3 ms 716 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 1424 KB Output is correct
2 Correct 29 ms 1560 KB Output is correct
3 Correct 57 ms 1576 KB Output is correct
4 Correct 102 ms 1548 KB Output is correct
5 Correct 21 ms 1608 KB Output is correct
6 Correct 73 ms 1544 KB Output is correct
7 Correct 45 ms 1540 KB Output is correct
8 Correct 13 ms 1532 KB Output is correct
9 Correct 12 ms 1440 KB Output is correct
10 Correct 12 ms 1560 KB Output is correct
11 Correct 6 ms 1484 KB Output is correct
12 Correct 7 ms 1476 KB Output is correct
13 Correct 7 ms 1572 KB Output is correct
14 Correct 12 ms 1568 KB Output is correct
15 Correct 8 ms 1588 KB Output is correct
16 Correct 7 ms 1612 KB Output is correct
17 Correct 8 ms 1564 KB Output is correct
18 Correct 123 ms 1188 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 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 5 ms 760 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 4 ms 752 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 748 KB Output is correct
8 Correct 4 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 3 ms 716 KB Output is correct
12 Incorrect 0 ms 460 KB WA in grader: Wrong returned array size
13 Halted 0 ms 0 KB -