Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 11,520 MiB 0,016 s OK
#2 3/3 11,516 MiB 0,000 s OK
#3 3/3 11,324 MiB 0,004 s OK
#4 3/3 11,516 MiB 0,004 s OK
#5 3/3 11,320 MiB 0,004 s OK
#6 3/3 11,520 MiB 0,004 s OK
#7 3/3 11,520 MiB 0,004 s OK
#8 3/3 11,320 MiB 0,000 s OK
#9 3/3 11,320 MiB 0,004 s OK
#10 3/3 11,324 MiB 0,010 s OK
#11 3/3 11,324 MiB 0,004 s OK
#12 3/3 11,520 MiB 0,010 s OK
#13 3/3 11,328 MiB 0,004 s OK
#14 3/3 11,328 MiB 0,004 s OK
#15 3/3 11,328 MiB 0,000 s OK
#16 3/3 11,523 MiB 0,004 s OK
#17 3/3 11,328 MiB 0,004 s OK
#18 3/3 11,547 MiB 0,000 s OK
#19 3/3 11,543 MiB 0,000 s OK
#20 3/3 11,344 MiB 0,010 s OK
#21 3/3 11,539 MiB 0,004 s OK
#22 3/3 11,438 MiB 0,010 s OK
#23 3/3 27,629 MiB 0,218 s OK
#24 3/3 22,785 MiB 0,224 s OK
#25 3/3 23,082 MiB 0,243 s OK
#26 3/3 16,793 MiB 0,154 s OK
#27 3/3 14,484 MiB 0,118 s OK
#28 3/3 23,441 MiB 0,194 s OK
#29 3/3 22,891 MiB 0,194 s OK
#30 3/3 16,949 MiB 0,136 s OK
#31 3/3 14,352 MiB 0,099 s OK
#32 3/3 13,535 MiB 0,106 s OK
#33 4/4 11,520 MiB 0,004 s OK

Ocenjevani program (Dolenjec.cpp):
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define maxn 111111

vector<int> st, comp[maxn], adj[maxn], pov[maxn];
int low[maxn], num[maxn], vis[maxn], comp_num[maxn], cnt, nn, g[maxn], ok[maxn], ans;

void DFS(int x){
    st.pb(x);
    num[x] = low[x] = ++cnt;
    vis[x] = 1;
    for(int v : adj[x]){
        if(num[v] == 0)
            DFS(v);
        
        if(vis[v])
            low[x] = min(low[x], low[v]);
    }
    
    if(low[x] == num[x]){
        nn++;
        int v;
        do{
            v = st.back();
            st.pop_back();
            vis[v] = 0;
            comp_num[v] = nn;
            comp[nn].pb(v);
                        
        } while(x != v);
    }
}

void DFS1(int x){
    ans = max(ans, ok[x]);
    for(int v : pov[x])
        DFS1(v);
}

int main(){ 
    int n, m, d, start;
    scanf("%d%d%d%d", &n, &m, &d, &start);
    for(int i = 0; i < d; i++){
        int x;
        scanf("%d", &x);
        g[x] = 1;                
    }
    
    for(int i = 0; i < m; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].pb(b);
    }
    
    for(int i = 1; i <= n; i++){
        if(num[i] == 0)
            DFS(i);
    }
    
    for(int i = 1; i <= nn; i++){
        for(int j : comp[i]){
            for(int k : adj[j]){
                if(comp_num[j] != comp_num[k])
                    pov[comp_num[j]].pb(comp_num[k]);
            }
        }
    }
    
    for(int i = 1; i <= n; i++){
        if(g[i]){
            int find = 0;
            for(int j : adj[i]){ 
                if(j == i){
                    find = 1;
                    break;                    
                }
            }
            if(find)
                ok[comp_num[i]] = 1;
        }
    }
    
    for(int i = 1; i <= nn; i++){
        int ghere = 0;
        for(int j : comp[i])
            ghere = max(ghere, g[j]);
        
        if(ghere && comp[i].size() > 1)
            ok[i] = 1;
    }
    
    ans = 0;
    DFS1(comp_num[start]);
    
    if(ans)
        printf("DA\n");
    else
        printf("NE\n");
}