Rezultati

Up. imeNalogaJezikRezultatČas oddaje
vlakectomaz-2018 Dolenjec C++ 100/100OK 10. maj '18 @ 18:25

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 6,059 MiB 0,000 s OK
#2 3/3 6,051 MiB 0,000 s OK
#3 3/3 6,180 MiB 0,004 s OK
#4 3/3 6,184 MiB 0,004 s OK
#5 3/3 6,051 MiB 0,004 s OK
#6 3/3 6,047 MiB 0,004 s OK
#7 3/3 6,184 MiB 0,004 s OK
#8 3/3 6,184 MiB 0,004 s OK
#9 3/3 6,184 MiB 0,000 s OK
#10 3/3 6,184 MiB 0,004 s OK
#11 3/3 6,051 MiB 0,004 s OK
#12 3/3 6,051 MiB 0,004 s OK
#13 3/3 6,055 MiB 0,004 s OK
#14 3/3 6,051 MiB 0,004 s OK
#15 3/3 6,051 MiB 0,004 s OK
#16 3/3 6,184 MiB 0,000 s OK
#17 3/3 6,051 MiB 0,000 s OK
#18 3/3 6,063 MiB 0,000 s OK
#19 3/3 6,195 MiB 0,010 s OK
#20 3/3 6,063 MiB 0,004 s OK
#21 3/3 6,063 MiB 0,010 s OK
#22 3/3 6,148 MiB 0,010 s OK
#23 3/3 15,203 MiB 0,293 s OK
#24 3/3 9,309 MiB 0,231 s OK
#25 3/3 9,188 MiB 0,232 s OK
#26 3/3 7,633 MiB 0,246 s OK
#27 3/3 7,359 MiB 0,258 s OK
#28 3/3 12,152 MiB 0,293 s OK
#29 3/3 9,188 MiB 0,274 s OK
#30 3/3 7,750 MiB 0,227 s OK
#31 3/3 7,219 MiB 0,209 s OK
#32 3/3 7,082 MiB 0,191 s OK
#33 4/4 6,180 MiB 0,000 s OK

Ocenjevani program (dolenjec.cc):
#include <iostream>
#include <vector>
using namespace std;

int rekurz(int tukaj, int gostiln_prej);

enum stavba_tip {stavba, gostilna};

struct stavba{
	vector <int> povezave;
	char tip;
	int st_gostiln; // -1, če ni vsebovan v ciklu
};

struct stavba stavbe[100005];

// DFS STACK
vector <int> S;
char najdeno=0;


int main(){
int n,m,d,q,i,j,a,b;
cin >> n >> m >> d >> q;

// INIT stavbe
for(i=1;i<n+1;i++){ stavbe[i].tip=0; stavbe[i].st_gostiln=-1; }

// BRANJE GOSTILN
for(i=0;i<d;i++){ cin >> a; stavbe[a].tip=1; }

// BRANJE povezav
for(i=0;i<m;i++){ cin >> a >> b; stavbe[a].povezave.push_back(b); }

rekurz(q, 0);

// PRINT REZULTAT
if(najdeno)cout << "DA\n";
else cout << "NE\n";

return 0;	
}

int rekurz(int tukaj, int gostiln_prej){
	int a, gostilne_sedaj;
	
	// NAJDENO
	if(najdeno)return 0;
	
	// OSVEŽIMO ŠT GOSTILN
	if( stavbe[tukaj].tip ) gostilne_sedaj=stavbe[tukaj].st_gostiln=gostiln_prej+1;
	else gostilne_sedaj=stavbe[tukaj].st_gostiln=gostiln_prej;
	
	// SOSEDJE
	for(int i=0;i<stavbe[tukaj].povezave.size();i++){
		a = stavbe[tukaj].povezave[i];
		
		// GOSTILNA SAMA S SEBOJ
		if( a == tukaj && stavbe[a].tip ){ najdeno=1; return 0; }
		
		// ČE ZAOBJAMEMO GOSTILNO NA ZAČETKU CIKLA
		
		// ČE ZAOBJAMEMO CIKEL Z GOSTILNO ali je GOSTILNA NA ZAČETKU
		char pogoj = (gostilne_sedaj > stavbe[a].st_gostiln) | stavbe[a].tip;
		if( pogoj && stavbe[a].st_gostiln>-1 ){ najdeno=1; return 0; }
		
		// NADALJUJEMO
		if( stavbe[a].st_gostiln==-1 ) rekurz( a, gostilne_sedaj );
		
		// ČE ZAOBJAMEMO CIKEL BREZ GOSTILNE
		// ne naredimo nič
		
		//S.push_back( a );
	}
	
	stavbe[tukaj].st_gostiln=-1;
	//S.pop_back();
}