Rezultati

Up. imeNalogaJezikRezultatČas oddaje
pspace-2017 Trgovec C++ 0/100Napaka med izvajanjem / ob izhodu (RTE) 11. maj '17 @ 17:16

Test Točke Porabljen spomin Porabljen čas Status
#1 0/3 263,816 MiB 0,516 s Prekoračen spomin
#2 0/3 263,852 MiB 0,534 s Prekoračen spomin
#3 0/3 263,855 MiB 0,504 s Prekoračen spomin
#4 0/3 263,852 MiB 0,522 s Prekoračen spomin
#5 0/3 263,855 MiB 0,528 s Prekoračen spomin
#6 0/3 263,852 MiB 0,534 s Prekoračen spomin
#7 0/3 263,855 MiB 0,522 s Prekoračen spomin
#8 0/3 263,816 MiB 0,528 s Prekoračen spomin
#9 0/3 263,816 MiB 0,528 s Prekoračen spomin
#10 0/3 263,816 MiB 0,534 s Prekoračen spomin
#11 0/3 263,816 MiB 0,522 s Prekoračen spomin
#12 0/3 263,859 MiB 0,528 s Prekoračen spomin
#13 0/3 7,828 MiB 0,010 s Napaka med izvajanjem / ob izhodu
#14 0/3 7,867 MiB 0,010 s Napaka med izvajanjem / ob izhodu
#15 0/3 7,871 MiB 0,010 s Napaka med izvajanjem / ob izhodu
#16 0/3 7,902 MiB 0,010 s Napaka med izvajanjem / ob izhodu
#17 0/3 7,895 MiB 0,010 s Napaka med izvajanjem / ob izhodu
#18 0/3 7,895 MiB 0,010 s Napaka med izvajanjem / ob izhodu
#19 0/3 7,988 MiB 0,010 s Klicana nedovoljena funkcija
Stderr:
userProg: malloc.c:2392: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
#20 0/3 264,008 MiB 0,540 s Prekoračen spomin
#21 4/4 27,875 MiB 0,402 s OK
#22 0/4 277,906 MiB 0,865 s Prekoračen spomin
#23 0/4 277,434 MiB 0,853 s Prekoračen spomin
#24 0/4 13,063 MiB 0,264 s Napaka med izvajanjem / ob izhodu
#25 0/4 11,000 MiB 0,234 s Napaka med izvajanjem / ob izhodu
#26 4/4 26,227 MiB 0,371 s OK
#27 0/4 277,395 MiB 0,816 s Prekoračen spomin
#28 0/4 13,133 MiB 0,251 s Napaka med izvajanjem / ob izhodu
#29 0/4 11,043 MiB 0,240 s Napaka med izvajanjem / ob izhodu
#30 0/4 265,914 MiB 0,727 s Prekoračen spomin

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

using namespace std;

#define MXN 100008

struct Scc {
    int n, nScc, vst[MXN], bln[MXN];
    vector<int> E[MXN], rE[MXN], vec;
    void init(int _n) {
        n = _n;
        for(int i=0;i<MXN;i++) {
            E[i].clear();
            rE[i].clear();
        }
    }

    void add_edge(int u, int v) {
        E[u].push_back(v);
        rE[v].push_back(u);
    }

    void DFS(int u) {
        vst[u] = 1;
        for(auto v: E[u]) {
            if(!vst[v]) DFS(v);
        }
        vec.push_back(u);
    }

    void rDFS(int u) {
        vst[u] = 1;
        bln[u] = nScc;
        for(auto v: rE[u]) {
            if(!vst[v]) rDFS(v);
        }
    }

    vector<set<int>> children;
    vector<int> parent;

    int dfs_components(int x, vector<int>& cache) {
        if(cache[x] != -1) return cache[x];

        int r = 1;
        for(int j : children[x]) {
            r = max(r, 1+dfs_components(j, cache));
        }

        cache[x] = r;
        return r;
    }

    int find_longest_path(int s) {
        children.resize(nScc);
        parent.resize(nScc);

        for(int u=0;u<n;u++) {
            for(auto v : E[u]) {
                children[bln[u]].insert(bln[v]);
                parent[v] = u;
            }
        }

        vector<int> dp(nScc);
        memset(dp.data(), -1, sizeof(int) * dp.size());

        return dfs_components(bln[s], dp);
    }

    bool solve(int s) {
        nScc = 0;
        vec.clear();
        memset(vst, 0, sizeof(vst));

        for(int i=0;i<n;i++) {
            if(!vst[i]) DFS(i);
        }
        reverse(vec.begin(), vec.end());
        memset(vst, 0, sizeof(vst));
        for(auto v : vec) {
            if(!vst[v]) {
                rDFS(v);
                nScc++;
            }
        }

        return find_longest_path(s) == nScc;
    }
} scc;

int main() {
    int n, m, s;
    cin>>n>>m>>s;
    s--;

    scc.init(n);

    for(int i=0;i<m;i++) {
        int u, v;
        cin>>u>>v;
        scc.add_edge(u-1, v-1);
    }

    bool sol = scc.solve(s);

    printf("%s\n", sol?"DA":"NE");

    return 0;
}