Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 5,992 MiB 0,004 s OK
#2 3/3 6,063 MiB 0,000 s OK
#3 3/3 6,063 MiB 0,004 s OK
#4 3/3 5,992 MiB 0,000 s OK
#5 3/3 5,992 MiB 0,000 s OK
#6 3/3 6,063 MiB 0,004 s OK
#7 3/3 5,992 MiB 0,000 s OK
#8 3/3 6,063 MiB 0,004 s OK
#9 3/3 6,059 MiB 0,010 s OK
#10 3/3 5,992 MiB 0,004 s OK
#11 3/3 5,992 MiB 0,010 s OK
#12 3/3 5,992 MiB 0,004 s OK
#13 3/3 5,992 MiB 0,004 s OK
#14 3/3 5,996 MiB 0,004 s OK
#15 3/3 6,066 MiB 0,010 s OK
#16 3/3 6,066 MiB 0,000 s OK
#17 3/3 5,996 MiB 0,004 s OK
#18 3/3 6,078 MiB 0,004 s OK
#19 3/3 6,012 MiB 0,010 s OK
#20 3/3 6,008 MiB 0,000 s OK
#21 3/3 6,008 MiB 0,000 s OK
#22 3/3 6,180 MiB 0,016 s OK
#23 3/3 15,734 MiB 0,273 s OK
#24 3/3 14,625 MiB 0,334 s OK
#25 3/3 14,469 MiB 0,381 s OK
#26 3/3 9,699 MiB 0,215 s OK
#27 3/3 8,645 MiB 0,227 s OK
#28 3/3 12,668 MiB 0,280 s OK
#29 3/3 11,105 MiB 0,286 s OK
#30 3/3 10,039 MiB 0,221 s OK
#31 3/3 8,645 MiB 0,221 s OK
#32 3/3 7,766 MiB 0,185 s OK
#33 4/4 5,984 MiB 0,004 s OK

Ocenjevani program (Dolenjec.cpp):
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define SIZE 100002

vector<int> adj[SIZE];
int vstopni_cas[SIZE];
int low[SIZE];
bool gostilna[SIZE];
bool specCase[SIZE];
bool visited[SIZE];
stack<int> S;
int cas;
bool OK;

void SCC(int v) {
	vstopni_cas[v] = low[v] = cas++;

	S.push(v);
	visited[v] = true;
	for (int i = 0; i < (int)adj[v].size(); i++) {
		if (OK) return;
		if (visited[adj[v][i]] == false) SCC(adj[v][i]);
		low[v] = min(low[v], low[adj[v][i]]);
	}
	if (OK) return;

	if (low[v] == vstopni_cas[v]) {
		int stComp = 0;
		bool g = false;
		while (1) {
			stComp++;
			if (gostilna[S.top()])
				g = true;
			int cc = S.top();
			visited[cc] = false;
			if (specCase[cc]) {
				OK = true;
				return;
			}

			S.pop();
			if (cc == v) break;
		}
		if (g && stComp > 1) {
			OK = true;
		}
	}
}


int main() {
	int N, M, D, Start, a, b;


	fill(vstopni_cas, vstopni_cas + SIZE, -1);
	memset(gostilna, false, sizeof gostilna);
	memset(specCase, false, sizeof specCase);
	memset(visited, false, sizeof visited);
	cas = 0;
	OK = false;

	cin >> N >> M >> D >> Start;

	for (int i = 0; i < D; i++) {
		cin >> a;
		gostilna[a] = true;
	}

	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		if (a == b && gostilna[a])
			specCase[a] = true;

		adj[a].push_back(b);
	}

	SCC(Start);

	if (OK) cout << "DA";
	else cout << "NE";

	//system("pause");
	return 0;
}