oj.uz

Submission #113837

# Submission time Handle Problem Language Result Execution time Memory
113837 2019-05-28T15:34:52 Z faustaadp Toy Train (IOI17_train) C++17
27 / 100
 2000 ms 50896 KB 
#include "train.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll m,n,a[5050],b[5050],cic[5050],nx[5050],i,TC1,putar[5050],j,TC3,TC4;
bool x[5050][5050];
bool y[5050][5050];
vector<ll> v[5050];
ll cek(ll aa)
{
	if(a[aa]==1)
	{
		if(b[aa]&&cic[aa])
			return 1;
		if(nx[aa])
			return cek(aa+1);
		return 0;
	}
	else
	{
		if(b[aa]==0&&cic[aa])
			return 0;
		if(nx[aa])
			return cek(aa+1);
		return 1;
	}
}
void dfs(ll aa,ll bb)
{
//	if(putar[aa])
//		return ;
	ll ii;
	for(ii=0;ii<v[bb].size();ii++)
		if(!x[aa][v[bb][ii]])
		{
			if(v[bb][ii]==aa)
			{
				if(b[aa])
					putar[aa]=1;
		//		return ;
			}
			x[aa][v[bb][ii]]=1;
			dfs(aa,v[bb][ii]);
		}
}
void dfs2(ll aa,ll bb)
{
//	if(putar[aa])
//		return ;
	ll ii;
	for(ii=0;ii<v[bb].size();ii++)
		if(!x[aa][v[bb][ii]])
		{
			x[aa][v[bb][ii]]=1;
			dfs2(aa,v[bb][ii]);
		}
}
void dfs3(ll aa,ll bb)
{
//	if(putar[aa])
//		return ;
	if(b[aa])return ;
	ll ii;
	for(ii=0;ii<v[bb].size();ii++)
		if(!y[aa][v[bb][ii]]&!b[v[bb][ii]])
		{
			if(aa==v[bb][ii])
				putar[aa]=1;
			y[aa][v[bb][ii]]=1;
			dfs3(aa,v[bb][ii]);
		}
}
std::vector<int> who_wins(std::vector<int> A, std::vector<int> r, std::vector<int> U, std::vector<int> V) 
{
	m=U.size();
	n=A.size();
	TC3=1;
	for(i=0;i<n;i++)a[i]=A[i];
	for(i=0;i<n;i++)if(!a[i])TC3=0;
	for(i=0;i<n;i++)b[i]=r[i];
	TC1=1;
	for(i=0;i<m;i++)
	{
		if(U[i]==V[i])
			cic[U[i]]=1;
		else
		if(U[i]+1==V[i])
			nx[U[i]]=1;
		else
			TC1=0;
		v[U[i]].pb(V[i]);
		//v[V[i]].pb(U[i]);
	}
	std::vector<int> res(n);
	if(TC1)
	{	
		for(int i = 0; i < n; i++)
			res[i] = cek(i);
	}
	else
	if(TC3)
	{
		for(i=0;i<n;i++)
		{
			//if(b[i])
			dfs(i,i);
		}
		for(i=0;i<n;i++)
			res[i]=0;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(x[i][j]&&putar[j])
				{
					res[i]=1;
					break;
				}
	}
	else
	{
		for(i=0;i<n;i++)
		{
			//if(b[i])
			dfs2(i,i);
			dfs3(i,i);
		}
		for(i=0;i<n;i++)
			res[i]=1;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(x[i][j]&&putar[j])
				{
					res[i]=0;
					break;
				}
	}
	return res;
}

Compilation message

train.cpp: In function 'void dfs(ll, ll)':
train.cpp:37:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[bb].size();ii++)
           ~~^~~~~~~~~~~~~
train.cpp: In function 'void dfs2(ll, ll)':
train.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[bb].size();ii++)
           ~~^~~~~~~~~~~~~
train.cpp: In function 'void dfs3(ll, ll)':
train.cpp:68:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[bb].size();ii++)
           ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 640 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 26364 KB Output is correct
2 Correct 321 ms 26232 KB Output is correct
3 Correct 321 ms 26104 KB Output is correct
4 Correct 1330 ms 26232 KB Output is correct
5 Correct 951 ms 26216 KB Output is correct
6 Correct 753 ms 26116 KB Output is correct
7 Correct 577 ms 26212 KB Output is correct
8 Correct 443 ms 26232 KB Output is correct
9 Correct 426 ms 26104 KB Output is correct
10 Correct 485 ms 25988 KB Output is correct
11 Correct 412 ms 26080 KB Output is correct
12 Correct 81 ms 25704 KB Output is correct
13 Correct 1385 ms 26360 KB Output is correct
14 Correct 1424 ms 26420 KB Output is correct
15 Correct 1409 ms 26360 KB Output is correct
16 Correct 1350 ms 26360 KB Output is correct
17 Correct 1440 ms 26360 KB Output is correct
18 Correct 526 ms 26112 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 26244 KB Output is correct
2 Correct 390 ms 50668 KB Output is correct
3 Correct 849 ms 50484 KB Output is correct
4 Correct 688 ms 40184 KB Output is correct
5 Correct 1083 ms 50680 KB Output is correct
6 Correct 910 ms 50564 KB Output is correct
7 Correct 952 ms 50256 KB Output is correct
8 Correct 623 ms 48544 KB Output is correct
9 Correct 84 ms 26744 KB Output is correct
10 Correct 1383 ms 30524 KB Output is correct
11 Correct 1373 ms 26988 KB Output is correct
12 Correct 1335 ms 31352 KB Output is correct
13 Correct 1330 ms 50896 KB Output is correct
14 Correct 755 ms 50860 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 39140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 6 ms 896 KB Output is correct
3 Correct 6 ms 1024 KB Output is correct
4 Correct 23 ms 1024 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 6 ms 1024 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 4 ms 896 KB Output is correct
12 Incorrect 2 ms 640 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -