Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 14,113 MiB 0,016 s OK
#2 3/3 14,117 MiB 0,016 s OK
#3 3/3 14,117 MiB 0,016 s OK
#4 3/3 14,117 MiB 0,016 s OK
#5 3/3 14,027 MiB 0,016 s OK
#6 3/3 14,117 MiB 0,016 s OK
#7 3/3 14,117 MiB 0,016 s OK
#8 3/3 14,031 MiB 0,016 s OK
#9 3/3 14,031 MiB 0,016 s OK
#10 3/3 14,117 MiB 0,016 s OK
#11 3/3 14,031 MiB 0,016 s OK
#12 3/3 14,035 MiB 0,016 s OK
#13 3/3 14,035 MiB 0,016 s OK
#14 3/3 14,035 MiB 0,016 s OK
#15 3/3 14,031 MiB 0,034 s OK
#16 3/3 14,137 MiB 0,016 s OK
#17 3/3 14,137 MiB 0,016 s OK
#18 3/3 14,047 MiB 0,016 s OK
#19 3/3 14,051 MiB 0,034 s OK
#20 3/3 14,137 MiB 0,022 s OK
#21 4/4 25,496 MiB 0,220 s OK
#22 4/4 21,582 MiB 0,196 s OK
#23 4/4 22,227 MiB 0,196 s OK
#24 4/4 18,082 MiB 0,148 s OK
#25 4/4 16,434 MiB 0,154 s OK
#26 4/4 22,137 MiB 0,250 s OK
#27 4/4 22,074 MiB 0,196 s OK
#28 4/4 18,113 MiB 0,142 s OK
#29 4/4 16,535 MiB 0,166 s OK
#30 4/4 15,742 MiB 0,118 s OK

Ocenjevani program (trgovec.cpp):
#include <cstdio>
#include <vector>
#include <deque>
#define pb push_back
#define vi vector<int>
using namespace std;

const int UNVISITED = -1;
const int N = 200000;

vi dfs_num, dfs_low, S, visited;
int dfsNumberCounter, numSCC;
vector<int> vtx[N];
vector<int> compVtx[N];
deque<int> dq;
int inDeg[N];

int inComp[N];
void trajanSCC(int u){
    dfs_low[u] = dfs_num[u] = dfsNumberCounter++;
    S.push_back(u);
    visited[u] = 1;
    for(int j = 0;j < vtx[u].size();j++){
        int v = vtx[u][j];
        if(dfs_num[v] == UNVISITED)
            trajanSCC(v);
        if(visited[v])
            dfs_low[u] = min(dfs_low[u],dfs_low[v]);
    }
    if(dfs_low[u] == dfs_num[u]){
        // nova povezana komponenta
        while(true){
            int v = S.back(); S.pop_back();
            visited[v] = 0;
            inComp[v] = numSCC;
            if(u == v) break;
        }
        ++numSCC;
        
    }
}


int main(){
    int n,m,s,a,b;
    scanf("%d %d %d",&n,&m,&s);
    s--;
    for(int i = 0;i < m;i++){
        scanf("%d %d",&a,&b);
        a--; b--;
        vtx[a].pb(b);
    }
    
    dfs_num.assign(N, UNVISITED);
    dfs_low.assign(N, 0);
    visited.assign(N, 0);
    dfsNumberCounter = numSCC = 0;
    for(int i = 0;i < n;i++){
        if(dfs_num[i] == UNVISITED)
            trajanSCC(i);
    }
    
    for(int i = 0;i < n;i++){
        for(int j = 0; j < vtx[i].size();j++){
            int v = vtx[i][j];
            if(inComp[i] != inComp[v]){
   //             printf("%d -> %d\n",inComp[i],inComp[v]);
                compVtx[inComp[i]].push_back(inComp[v]);
                inDeg[inComp[v]]++;
            }
        }
    }
    
   // for(int i = 0;i < n;i++)
   //     printf("%d %d\n",i,inComp[i]);
    
    if(inDeg[inComp[s]] > 0)
    {
        printf("NE\n");
        return 0;
    }
    for(int i = 0; i < numSCC;i++){
        if(inDeg[i] == 0)
            dq.pb(i);
    }
    
    int pathLen = 0;
    while(!dq.empty()){
        int len = dq.size();
        pathLen++;
        
      //  printf("iteration %d: \n",pathLen);
        for(int i = 0;i < len;i++){
            int v = dq.front();
         //   printf("\t%d\n",v);
            dq.pop_front();
            for(int j = 0;j < compVtx[v].size();j++)
                if(--inDeg[compVtx[v][j]] == 0)
                    dq.pb(compVtx[v][j]);
        }
    }
   // printf("%d %d\n",pathLen,numSCC);
    if(pathLen == numSCC)
        printf("DA\n");
    else printf("NE\n");
    return 0;
}