Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 3,070 MiB 0,004 s OK
#2 3/3 3,074 MiB 0,004 s OK
#3 3/3 3,098 MiB 0,004 s OK
#4 3/3 3,098 MiB 0,004 s OK
#5 3/3 3,066 MiB 0,004 s OK
#6 3/3 3,094 MiB 0,004 s OK
#7 3/3 3,074 MiB 0,004 s OK
#8 3/3 3,074 MiB 0,004 s OK
#9 3/3 3,098 MiB 0,004 s OK
#10 3/3 3,074 MiB 0,004 s OK
#11 3/3 3,090 MiB 0,004 s OK
#12 3/3 3,094 MiB 0,004 s OK
#13 3/3 3,074 MiB 0,004 s OK
#14 3/3 3,098 MiB 0,004 s OK
#15 3/3 3,074 MiB 0,004 s OK
#16 3/3 3,152 MiB 0,004 s OK
#17 3/3 3,109 MiB 0,004 s OK
#18 3/3 3,102 MiB 0,004 s OK
#19 3/3 3,133 MiB 0,004 s OK
#20 3/3 3,199 MiB 0,016 s OK
#21 4/4 32,602 MiB 0,371 s OK
#22 4/4 23,820 MiB 0,371 s OK
#23 4/4 25,430 MiB 0,378 s OK
#24 4/4 11,988 MiB 0,251 s OK
#25 4/4 7,484 MiB 0,221 s OK
#26 4/4 26,555 MiB 0,401 s OK
#27 4/4 23,961 MiB 0,378 s OK
#28 4/4 12,117 MiB 0,263 s OK
#29 4/4 7,465 MiB 0,239 s OK
#30 4/4 5,754 MiB 0,204 s OK

Ocenjevani program (trgovec.cpp):
#include <algorithm>
#include <array>
#include <complex>
#include <cmath>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;

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

void scc_util(int u, const vector<vi>& graf, vvi& comps) {
    static int dfs_num_counter = 1;
    low[u] = dfs_num[u] = dfs_num_counter++;
    S.push(u);
    
    for (int v : graf[u]) {
        if (dfs_num[v] == 0)
            scc_util(v, graf, comps);
        if (dfs_num[v] != -1) 
            low[u] = min(low[u], low[v]);
    }
    
    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 scc(const vector<vi>& graf, vvi& comps, vector<map<int, int>>& dag) {
    int n = graf.size();
    low.assign(n, 0);
    dfs_num.assign(n, 0);
    component.assign(n, -1);
    
    for (int i = 0; i < n; ++i) {
        if (dfs_num[i] == 0) {
            scc_util(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]) {
                dag[component[u]][component[v]] += 1;
            }
        }
    }
}

int main() { 
    int n, m, s, a, b;
    cin >> n >> m >> s;
    s--;
    vector<vi> graf(n);
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        a--; b--;
        if (a == b) continue;
        graf[a].push_back(b);
    }
    
    for (int i = 0; i < n; ++i) {
        sort(graf[i].begin(), graf[i].end());
        auto it = unique(graf[i].begin(), graf[i].end());
        graf[i].resize(it - graf[i].begin());
    }
    
//     for (int i = 0; i < graf.size(); ++i)  {
//         cout << i << ": ";
//         for (int v : graf[i]) {
//             cout << v << " ";
//         }
//         cout << "\n";
//     }
//         cout << "--------\n";
    
    vector<map<int, int>> dag;
    vvi comps;
    scc(graf, comps, dag);
    
        
//     for (int i : component) {
//         cout << i << ' ';
//     } cout << '\n';
    
    int start = component[s];
//     cout << "start: " << start << "\n";
//     
    vi maxs(n, 1);
    
//     for (int i = 0; i < dag.size(); i++) {
//         cout << i <<": ";
//         for (auto& x : dag[i]) {
//             cout << x.first << " ";
//         }
//         cout << "\n";
//     }

    
    for (int i = 0; i < dag.size(); i++) {
        for (const auto& x : dag[i]) {
            maxs[i] = max(maxs[i], maxs[x.first]+1);
        }
    }
    
    
//     for (int i = 0; i < dag.size(); ++i) {
//         cout << maxs[i] << " ";
//     }
//     cout << "\n";
    if (maxs[start] == dag.size())
        cout << "DA\n";
    else 
        cout << "NE\n";
    
        return 0;
}