oj.uz

Submission #257168

# Submission time Handle Problem Language Result Execution time Memory
257168 2020-08-03T16:49:16 Z GREGOIRELC Toy Train (IOI17_train) C++14
15 / 100
 2000 ms 1024 KB 
#include "train.h"
#include <iostream>

using namespace std;

const int MAX_NOEUD = 5e3;
const int MAX_ARC = 2e4;

int nbNoeud, nbArc;
bool estProprietaire[MAX_NOEUD];
bool estRechargeable[MAX_NOEUD];
bool dp[MAX_NOEUD];
vector<int> graphe[MAX_NOEUD];
vector<int> pile;
vector<int> result;

bool DFS(int curNoeud)
{
	if(dp[curNoeud])
	{
		for(int i = (int)pile.size() - 1; i > -1; i--)
		{
			if(estRechargeable[pile[i]])
			{
				return true;
			}
			if(pile[i] == curNoeud)
			{
				return false;
			}
		}
	}
	dp[curNoeud] = true;
	pile.push_back(curNoeud);
	bool result = !estProprietaire[curNoeud];
	for(int voisin : graphe[curNoeud])
	{
		bool val = DFS(voisin);
		if(!val && !estProprietaire[curNoeud])
		{
			result = false;
			break;
		}
		if(val && estProprietaire[curNoeud])
		{
			result = true;
			break;
		}
	}
	pile.pop_back();
	dp[curNoeud] = false;
	if(graphe[curNoeud].size() == 0)
	{
		return false;
	}
	return result;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
	nbNoeud = (int)a.size();
	nbArc = (int)u.size();
	
	for(int iNoeud = 0; iNoeud < nbNoeud; iNoeud++)
	{
		if(a[iNoeud] == 1)
		{
			estProprietaire[iNoeud] = true;
		}
		if(r[iNoeud])
		{
			estRechargeable[iNoeud] = true;
		}
	}
	for(int iArc = 0; iArc < nbArc; iArc++)
	{
		graphe[u[iArc]].push_back(v[iArc]);
	}

	for(int iDep = 0; iDep < nbNoeud; iDep++)
	{
		if(DFS(iDep))
		{
			result.push_back(1);
		}
		else
		{
			result.push_back(0);
		}
		pile.clear();
		for(int i = 0; i < nbNoeud; i++)
		{
			dp[i] = false;
		}
	}
	return result;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 888 KB Output is correct
2 Correct 16 ms 896 KB Output is correct
3 Correct 18 ms 896 KB Output is correct
4 Correct 16 ms 1024 KB Output is correct
5 Correct 18 ms 896 KB Output is correct
6 Correct 18 ms 896 KB Output is correct
7 Correct 15 ms 896 KB Output is correct
8 Correct 19 ms 896 KB Output is correct
9 Correct 17 ms 896 KB Output is correct
10 Correct 17 ms 896 KB Output is correct
11 Correct 17 ms 896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 512 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 512 KB Output is correct
20 Correct 1 ms 384 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 888 KB Output is correct
2 Correct 16 ms 896 KB Output is correct
3 Correct 18 ms 896 KB Output is correct
4 Correct 16 ms 1024 KB Output is correct
5 Correct 18 ms 896 KB Output is correct
6 Correct 18 ms 896 KB Output is correct
7 Correct 15 ms 896 KB Output is correct
8 Correct 19 ms 896 KB Output is correct
9 Correct 17 ms 896 KB Output is correct
10 Correct 17 ms 896 KB Output is correct
11 Correct 17 ms 896 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 512 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 512 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 0 ms 512 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 0 ms 384 KB Output is correct
30 Correct 0 ms 512 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Execution timed out 2085 ms 1024 KB Time limit exceeded
33 Halted 0 ms 0 KB -