Rezultati

Up. imeNalogaJezikRezultatČas oddaje
CDXX-2017 Trgovec C++ 0/100Napačen odgovor (WA) 11. maj '17 @ 17:52

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 3,109 MiB 0,004 s OK
#2 3/3 3,086 MiB 0,004 s OK
#3 3/3 3,090 MiB 0,004 s OK
#4 3/3 3,086 MiB 0,004 s OK
#5 3/3 3,117 MiB 0,004 s OK
#6 3/3 3,090 MiB 0,004 s OK
#7 3/3 3,109 MiB 0,004 s OK
#8 3/3 3,086 MiB 0,004 s OK
#9 3/3 3,086 MiB 0,004 s OK
#10 3/3 3,113 MiB 0,004 s OK
#11 3/3 3,113 MiB 0,004 s OK
#12 3/3 3,117 MiB 0,004 s OK
#13 0/3 3,121 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#14 0/3 3,090 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#15 3/3 3,090 MiB 0,004 s OK
#16 0/3 3,094 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#17 0/3 3,117 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#18 0/3 3,094 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#19 3/3 3,098 MiB 0,004 s OK
#20 3/3 3,246 MiB 0,022 s OK
#21 0/4 3,992 MiB 0,197 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#22 0/4 3,996 MiB 0,197 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#23 0/4 3,996 MiB 0,197 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#24 0/4 3,996 MiB 0,197 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#25 4/4 5,980 MiB 0,234 s OK
#26 4/4 3,996 MiB 0,197 s OK
#27 4/4 4,031 MiB 0,197 s OK
#28 4/4 4,035 MiB 0,197 s OK
#29 0/4 5,984 MiB 0,246 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#30 0/4 5,266 MiB 0,234 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>

Ocenjevani program (main.cpp):
#include <cstdio>
#include <list>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int N,M,S;


struct pov{
	int from, to;
};

struct classCMP{
	bool operator() (const struct pov &lhs, const struct pov &rhs) const
	{ 
		if(lhs.from == rhs.from)
			return lhs.to < rhs.to;	
		return lhs.from < rhs.from;
	}
};

vector<struct pov> mySet;
vector<int> visited;
bool indicator = false;

bool exists(int search)
{
	int start = 0, end = visited.size(),mid,el;
	bool exists = false;
	while(start < end)
	{
		mid = (start + end) / 2;
		el = visited[mid];
		if(el == search){
			exists = true;
			break;
		}
		if(el < search){
			start = mid+1;
		}

		if(el > search){
			end = mid-1;
		}
	}
	return exists;
}

int findIndex(int search)
{
	int start = 0, end = mySet.size(),mid,el;
	bool exists = false;
	while(start < end)
	{
		mid = (start + end) / 2;
		el = mySet[mid].from;
		if(el == search){
			exists = true;
			break;
		}
		if(el < search){
			start = mid+1;
		}

		if(el > search){
			end = mid-1;
		}
	}
	if(exists)
	{
		for(;mySet[mid].from == search;mid--);
		return mid+1;
	}
	return -1;
}

void continueRoute(int current)
{
	//cout<<current<<endl;
	visited.push_back(current); // dodaj trenutno v visited
	if(visited.size() >= N)
	{
		indicator = true;
		return;
	}
	bool jeZe = false;
	int index = findIndex(current);
	if(index >= 0)
		for(int i=index;mySet[i].from==current;i++)// poklici vse pod
		{
				//cout<<mySet[i].from<<" "<<mySet[i].to<<endl;
				jeZe = true;
				if(!exists(mySet[i].to))
				{
					continueRoute(mySet[i].to);
				}
		}
	visited.pop_back();// odstrani iz visited
}



int main()
{
	cin >> N >> M >> S;
	//visited.resize(M);
	struct pov tmp;
	for(int i=0;i<M;i++)
	{
		cin >> tmp.from >> tmp.to;
		mySet.push_back(tmp);
	}
	sort(mySet.begin(),mySet.end(),classCMP());
	
	continueRoute(S);
	if(indicator)
		cout<<"DA"<<endl;
	else
		cout<<"NE"<<endl;
	return 0;
}