Rezultati

Up. imeNalogaJezikRezultatČas oddaje
tabs-2018 Dolenjec C++ 0/100Napaka med izvajanjem / ob izhodu (RTE) 10. maj '18 @ 17:53

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 5,402 MiB 0,004 s OK
#2 3/3 5,332 MiB 0,000 s OK
#3 3/3 5,332 MiB 0,004 s OK
#4 3/3 5,402 MiB 0,000 s OK
#5 3/3 5,406 MiB 0,004 s OK
#6 3/3 5,391 MiB 0,004 s OK
#7 3/3 5,398 MiB 0,000 s OK
#8 3/3 5,402 MiB 0,000 s OK
#9 3/3 5,402 MiB 0,004 s OK
#10 3/3 5,402 MiB 0,000 s OK
#11 3/3 5,332 MiB 0,004 s OK
#12 3/3 5,336 MiB 0,000 s OK
#13 3/3 5,398 MiB 0,000 s OK
#14 3/3 5,328 MiB 0,000 s OK
#15 3/3 5,336 MiB 0,000 s OK
#16 3/3 5,402 MiB 0,004 s OK
#17 3/3 5,398 MiB 0,004 s OK
#18 3/3 5,348 MiB 0,000 s OK
#19 3/3 5,418 MiB 0,004 s OK
#20 3/3 5,418 MiB 0,004 s OK
#21 3/3 5,348 MiB 0,000 s OK
#22 3/3 5,664 MiB 0,010 s OK
#23 0/3 8,219 MiB 0,189 s Napaka med izvajanjem / ob izhodu
#24 3/3 8,945 MiB 0,231 s OK
#25 3/3 8,859 MiB 0,231 s OK
#26 3/3 8,531 MiB 0,203 s OK
#27 3/3 8,543 MiB 0,227 s OK
#28 0/3 6,789 MiB 0,126 s Napaka med izvajanjem / ob izhodu
#29 3/3 8,727 MiB 0,238 s OK
#30 3/3 8,578 MiB 0,203 s OK
#31 3/3 8,492 MiB 0,197 s OK
#32 3/3 8,516 MiB 0,197 s OK
#33 4/4 5,402 MiB 0,004 s OK

Ocenjevani program (main.cpp):
#include <algorithm>
#include <array>
#include <complex>
#include <cmath>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#include <list>

using namespace std;

int n,m,d,q0;

struct povezava{
	int from, to;
};

const int MAX = 100000;
bool gostilne[MAX] = {false};
bool visited[MAX] = {false};
stack<int> order;
list<int> sosedi[MAX];

bool cycle = false;

bool cycleExists(int to)
{
	bool gostilna = false;
	stack<int> pom;
	int curr;
	
	while(true)
	{
		curr = order.top();
		//cout<<"STACKCURR:"<<curr<<endl;
		pom.push(curr);
		order.pop();
		if(gostilne[curr]) 
		{
			gostilna = true;
			break;
		}
		if(curr == to) break;
	}
	while(!pom.empty())
	{
		curr = pom.top();
		pom.pop();
		order.push(curr);
	}

	return gostilna;
}

void goFetch(int curr)
{
	if(cycle) return;
	//cout<<"CURR:"<<curr<<endl;
	order.push(curr);
	list<int> s = sosedi[curr];
	//cout<<"SIZE:"<<s.size()<<endl;
	if(s.size() > 0)
	for(list<int> :: iterator it = s.begin(); it!=s.end(); ++it)
	{
		//cout<<"SOSEDI:"<<*it<<endl;
		if(visited[*it] == true)
		{
			if(cycleExists(*it))
			{
				cycle = true;
				return;
			}
				//preveri vse točke v ciklu če je vsaj 1 gostilna
		}
		else
		{
			visited[*it] = true;
			goFetch(*it);
		}

	}
	
}

int main()
{
	cin>>n>>m>>d>>q0; 
	int read,read2, i;
	for(i=0; i<d; i++)
	{
		cin>>read;  
		gostilne[read] = true;
	}
	for(i=0; i<m; i++)
	{
		cin>>read>>read2;
		sosedi[read].push_back(read2);
	}
	
	/*for(i=0; i<n; i++)
	{
		list<int> s = sosedi[i];
		cout<<i<<":";
		for(list<int> :: iterator it = s.begin(); it!=s.end(); ++it)
		{
			cout<<*it<<"\t";
		}
		cout<<endl;
	}*/
	
	visited[q0] = true;
	
	goFetch(q0);
	
	if(cycle) cout<<"DA"<<endl;
	else cout<<"NE"<<endl;
	
	return 0;
}