Rezultati

Up. imeNalogaJezikRezultatČas oddaje
vlakectomaz-2018 Nič nas ne sme presenetiti! C++ 0/100Prekoračen čas (TLE) 19. apr '18 @ 20:04

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 2,738 MiB 0,000 s OK
#2 12/12 2,594 MiB 0,033 s OK
#3 12/12 2,535 MiB 0,000 s OK
#4 12/12 8,992 MiB 0,217 s OK
#5 13/13 2,535 MiB 0,000 s OK
#6 0/13 8,711 MiB 4,511 s Prekoračen čas
#7 0/13 8,680 MiB 4,544 s Prekoračen čas
#8 0/13 8,953 MiB 4,532 s Prekoračen čas

Ocenjevani program (nic.cc):
#include <stdio.h>
#include <queue>
#include <vector>


struct xy { int a,x;};

struct xy xymake(int x, int y){ xy a={x,y}; return a;}

struct mesto{
	std::vector <int> A;
	char jane;
	char obiskan;
};

int main(){
int vozli, primeri, primeri_i, i, j, a, b, stevec_mest, stevec_obiskanih_mest;

scanf("%d %d ", &vozli, &primeri);

struct mesto mesta[vozli+1];

// BEREMO VOZLE
for(i=0;i<vozli-1;i++){
	scanf("%d %d ",&a, &b);
	mesta[a].A.push_back(b);
	mesta[b].A.push_back(a);
}

// BEREMO PRIMERE
for(primeri_i=0; primeri_i<primeri;primeri_i++){
	// spraznemo vse
	for(i=0;i<vozli;i++) { mesta[i+1].jane=0; mesta[i+1].obiskan=0; }
	
	// Zapišemo v jane
	scanf("%d ", &stevec_mest);
	for(i=0;i<stevec_mest;i++) { scanf("%d ", &a); mesta[a].jane=1;}
	
	//BFS
	std::queue <int> Q;
	// Začnemo pri enem mestu, ki je vključeno
	Q.push(a);
	mesta[a].obiskan=1;
	stevec_obiskanih_mest=1;
	
	while(true){
		// Nimamo nikamor za iti
		if(Q.empty())break;
		a=Q.front();
		Q.pop();
		
		//Preveri možne sosede
		for(i=0;i<mesta[a].A.size();i++){

			// Element
			b = mesta[a].A[i];
			// jane nastavljen, če ja, lahko potujemo tja!
			if( mesta[b].jane==1 && mesta[b].obiskan==0) {
				stevec_obiskanih_mest++;
				Q.push(b);
				mesta[b].obiskan=1;
			}
		}
	}
	
	if(stevec_mest == stevec_obiskanih_mest) printf("ALAAAARHM\n");
	else printf("NASLEDNJI\n");
	
}
return 0;
}