Rezultati

Up. imeNalogaJezikRezultatČas oddaje
muzik-2018 Dolenjec C++ 0/100Napaka med izvajanjem / ob izhodu (RTE) 10. maj '18 @ 20:08

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 3,051 MiB 0,000 s OK
#2 0/3 2,809 MiB 0,004 s Napaka med izvajanjem / ob izhodu
#3 3/3 3,051 MiB 0,004 s OK
#4 3/3 3,043 MiB 0,004 s OK
#5 3/3 3,051 MiB 0,000 s OK
#6 3/3 3,121 MiB 0,000 s OK
#7 0/3 3,121 MiB 0,000 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#8 3/3 2,996 MiB 0,000 s OK
#9 3/3 2,996 MiB 0,000 s OK
#10 3/3 3,051 MiB 0,004 s OK
#11 0/3 3,121 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#12 3/3 3,055 MiB 0,000 s OK
#13 3/3 3,113 MiB 0,000 s OK
#14 3/3 3,125 MiB 0,000 s OK
#15 0/3 2,934 MiB 0,004 s Napaka med izvajanjem / ob izhodu
#16 0/3 2,855 MiB 0,000 s Napaka med izvajanjem / ob izhodu
#17 3/3 3,055 MiB 0,004 s OK
#18 0/3 2,965 MiB 0,004 s Napaka med izvajanjem / ob izhodu
#19 0/3 2,969 MiB 0,004 s Napaka med izvajanjem / ob izhodu
#20 0/3 2,969 MiB 0,004 s Napaka med izvajanjem / ob izhodu
#21 0/3 2,961 MiB 0,000 s Napaka med izvajanjem / ob izhodu
#22 3/3 3,293 MiB 0,016 s OK
#23 0/3 19,027 MiB 0,244 s Napaka med izvajanjem / ob izhodu
#24 0/3 14,633 MiB 0,303 s Napaka med izvajanjem / ob izhodu
#25 0/3 20,148 MiB 0,279 s Napaka med izvajanjem / ob izhodu
#26 0/3 9,996 MiB 0,227 s Napaka med izvajanjem / ob izhodu
#27 3/3 7,820 MiB 0,233 s OK
#28 0/3 16,266 MiB 0,243 s Napaka med izvajanjem / ob izhodu
#29 0/3 20,801 MiB 0,261 s Napaka med izvajanjem / ob izhodu
#30 3/3 12,324 MiB 0,257 s OK
#31 3/3 7,836 MiB 0,251 s OK
#32 0/3 6,391 MiB 0,215 s Napaka med izvajanjem / ob izhodu
#33 0/4 2,809 MiB 0,004 s Napaka med izvajanjem / ob izhodu

Ocenjevani program (main.cpp):
namespace{
}


#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <algorithm>
#include <map>

using namespace std;

vector<int> low;
vector<int> dfs_num;
stack<int> S;
vector<int> component;

void strongly_connected_components_internal(int u, const vector<vector<pair<int,int> > > & graf, vector<vector<int> > & comps){

    static int dfs_num_counter = 1;
    low[u] = dfs_num[u] = dfs_num_counter++;
    S.push(u);

    for(pair<int, int> v: graf[u]){
        if(dfs_num[v.first] == 0){
            strongly_connected_components_internal(v.first, graf, comps);
        }if(dfs_num[v.first] != -1){
            low[u] = min(low[u], low[v.first]);
        }
    }

    if(low[u] == dfs_num[u]){
        int cnum = comps.size();
        comps.push_back({});
        int w;
        do{
            w = S.top();
            S.pop();
            comps.back().push_back(w);
            component[w] = cnum;
            dfs_num[w] -=1;
        }while(w != u);
    }
}


void strongly_connected_components(const vector<vector<pair<int,int>>> &graf, vector<vector<int>> &comps, vector<map<int,int>> & dag){
    int n = graf.size();
    low.assign(n, 0);
    dfs_num.assign(n,0);
    component.assign(n, -1);
    //return;
    for(int i = 0; i < n; ++i){
        if(dfs_num[i] == 0){
            strongly_connected_components_internal(i, graf, comps);
        }
    }

    dag.resize(comps.size());
    for(int u = 0; u < n; ++u){
        for(const auto & v : graf[u]){
            if(component[u] != component[v.first]){
                dag[component[u]][component[v.first]] += v.second;
            }
        }
    }

}

int main(){
    int N, M, D, Q;
    cin >> N >> M >> D >> Q;
    vector<vector<pair<int,int> > > graf;
    vector<int> gostile;
    gostile.reserve(D);
    graf.reserve(N);
    vector<bool> gost;
    vector<bool> self;
    gost.reserve(N);
    for(int j = 0; j < N; ++j){
        vector<pair<int,int> > temp;
        graf.push_back(temp);
        gost.push_back(0);
        self.push_back(0);
    }
    for(int j = 0; j < D; ++j){
        int t;
        cin >> t;
        gostile.push_back(t-1);
        gost[t-1] = 1;
    }
    for(int j = 0; j < M; ++j){
        int from, to;
        cin >>from >> to;
        if(from == to){
            self[from-1] = 1;
        }
        graf[from-1].push_back(make_pair(to-1, 1));
    }
    vector<vector<int>> comps;
    vector<map<int,int>> dag;

    strongly_connected_components(graf, comps, dag);
    // Sprehodi DAG
    stack<int> sta;
    vector<bool> vis;
    vis.reserve(comps.size());
    for(int j = 0; j < comps.size(); ++j){
        vis.push_back(0);
    }
    int temp = -1;
    for(int j = 0; j < comps.size(); ++j){
        for(int i = 0; i < comps[j].size(); ++i){
            if(comps[j][i] == Q-1){
                temp = j;
                goto out;
            }
        }
    }
    if(temp == -1){
        cout << "NE\n";
        return 0;
    }
    out:
    sta.push(temp);
    vis[temp] = 1;
    while(sta.size()){
        int cur = sta.top();
        sta.pop();
        vis[cur] = 1;
        for(int j = 0; j < comps[cur].size(); ++j){
            if(gost[comps[cur][j]]){
                if(comps[cur].size() > 1 || self[comps[cur][j]]){
                    cout << "DA\n";
                    return 0;
                }

            }
        }
        auto m = dag[cur];
        for(const auto & kv : m){
            int key = kv.first;
            if(!vis[key]){
                sta.push(key);
            }
        }


    }


    cout << "NE\n";

    return 0;
}