Rezultati

Up. imeNalogaJezikRezultatČas oddaje
koklja-2017 Trgovec C++ 100/100OK 11. maj '17 @ 19:29

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 9,098 MiB 0,010 s OK
#2 3/3 9,059 MiB 0,010 s OK
#3 3/3 9,094 MiB 0,010 s OK
#4 3/3 9,094 MiB 0,010 s OK
#5 3/3 9,098 MiB 0,010 s OK
#6 3/3 9,059 MiB 0,010 s OK
#7 3/3 9,094 MiB 0,010 s OK
#8 3/3 9,059 MiB 0,010 s OK
#9 3/3 9,055 MiB 0,010 s OK
#10 3/3 9,098 MiB 0,010 s OK
#11 3/3 9,059 MiB 0,010 s OK
#12 3/3 9,063 MiB 0,010 s OK
#13 3/3 9,102 MiB 0,010 s OK
#14 3/3 9,063 MiB 0,010 s OK
#15 3/3 9,098 MiB 0,010 s OK
#16 3/3 9,121 MiB 0,016 s OK
#17 3/3 9,121 MiB 0,010 s OK
#18 3/3 9,117 MiB 0,010 s OK
#19 3/3 9,078 MiB 0,010 s OK
#20 3/3 9,211 MiB 0,016 s OK
#21 4/4 20,723 MiB 0,208 s OK
#22 4/4 18,836 MiB 0,190 s OK
#23 4/4 18,707 MiB 0,202 s OK
#24 4/4 12,805 MiB 0,130 s OK
#25 4/4 11,379 MiB 0,124 s OK
#26 4/4 17,465 MiB 0,196 s OK
#27 4/4 16,703 MiB 0,178 s OK
#28 4/4 12,930 MiB 0,124 s OK
#29 4/4 11,352 MiB 0,118 s OK
#30 4/4 10,703 MiB 0,106 s OK

Ocenjevani program (trgovec.cpp):
#include <iostream>
#include <complex>
#include <iomanip>
#include <climits>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>

#define FOR(i,n) for(int i=0,_n=n;i<_n;i++)
#define FORR(i,s,n) for(int i=s,_n=n;i<_n;i++)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define fs first
#define sec second
#define fi first
#define se second
#define INF (1LL<<50LL)

#define maxn 100000

using namespace std;
typedef long long ll;

const ll MOD = 1000000007LL;

vi graf[maxn+10];
int num[maxn+10];
int low[maxn+10];
bool visited[maxn+10];
vi S;
int cnt,nscc;

vi dag[maxn+10];
int n,m,s;
int glkomp;
//vi komponente[maxn+10];
int komponenta[maxn+10];
int longest[maxn+10];

void dfs(int u){
	low[u]=num[u]=cnt++;
	S.pb(u);
	visited[u]=1;
	FOR(j,graf[u].size()){
		int v = graf[u][j];
		if(num[v]==-1)dfs(v);
		if(visited[v])low[u]=min(low[u],low[v]);
	}
	if(low[u]==num[u]){
		nscc++;
		while(1){
			int v=S.back();
			S.pop_back();
			visited[v]=0;
			if(v==s)glkomp=nscc;
			//komponente[nscc].pb(v);
			komponenta[v]=nscc;
			if(u==v)break;
		}
	}
}

void dp(int curr){
	int dolga=0;
	FOR(i,dag[curr].size()){
		int v=dag[curr][i];
		if(longest[v]==0)dp(v);
		dolga=max(dolga,longest[v]);
	}
	dolga++;
	longest[curr]=dolga;
}

int main(){
	scanf("%d%d%d",&n,&m,&s);
	FOR(i,m){
		int a,b;
		scanf("%d%d",&a,&b);
		graf[a].pb(b);
	}
	memset(num,-1,sizeof(num));
	memset(low,0,sizeof(low));
	memset(visited,0,sizeof(visited));
	cnt=nscc=0;
	FORR(i,1,n+1)if(num[i]==-1)dfs(i);
	FORR(i,1,n+1){
		FOR(j,graf[i].size()){
			int v=graf[i][j];
			if(komponenta[v]==komponenta[i])continue;
			dag[komponenta[i]].pb(komponenta[v]);
		}
	}
	memset(longest,0,sizeof(longest));
	dp(glkomp);
	if(longest[glkomp]==nscc)printf("DA\n");
	else printf("NE\n");
	return 0;
}