Rezultati

Up. imeNalogaJezikRezultatČas oddaje
zerodays-2017 Trgovec C++ 0/100Napačen odgovor (WA) 11. maj '17 @ 18:48

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 3,094 MiB 0,004 s OK
#2 0/3 3,070 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#3 0/3 3,070 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#4 3/3 3,094 MiB 0,004 s OK
#5 3/3 3,094 MiB 0,004 s OK
#6 0/3 3,070 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#7 0/3 3,070 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#8 0/3 3,066 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#9 0/3 3,086 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#10 3/3 3,094 MiB 0,004 s OK
#11 3/3 3,105 MiB 0,004 s OK
#12 3/3 3,082 MiB 0,004 s OK
#13 3/3 3,094 MiB 0,004 s OK
#14 3/3 3,074 MiB 0,004 s OK
#15 3/3 3,082 MiB 0,004 s OK
#16 3/3 3,125 MiB 0,004 s OK
#17 3/3 3,125 MiB 0,004 s OK
#18 3/3 3,117 MiB 0,004 s OK
#19 3/3 3,133 MiB 0,004 s OK
#20 3/3 3,988 MiB 0,028 s OK
#21 4/4 21,207 MiB 0,335 s OK
#22 4/4 21,207 MiB 0,366 s OK
#23 4/4 21,281 MiB 0,390 s OK
#24 4/4 16,734 MiB 0,341 s OK
#25 4/4 15,215 MiB 0,342 s OK
#26 4/4 21,219 MiB 0,317 s OK
#27 4/4 21,180 MiB 0,299 s OK
#28 4/4 16,613 MiB 0,317 s OK
#29 4/4 15,117 MiB 0,317 s OK
#30 4/4 13,566 MiB 0,330 s OK

Ocenjevani program (trgovec.cpp):
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>

using namespace std;

int main() {
    int n, m, start;
    cin >> n >> m >> start;
    
    start--;
    
    vector<set<int>> g(n, set<int>());
    vector<set<int>> rg(n, set<int>());
    
    int koncni = -1;
        
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        g[a].insert(b);
        rg[b].insert(a);
    }
            
    for (int i = 0; i < n; ++i) {
        if (g[i].size() == 0) {
            if (koncni != -1) {
                cout << "NE" << endl;
                return 0;
            }
            koncni = i;
        }
    }
    
    vector<bool> visited(n, false);
    visited[start] = true;
    
    while (koncni != -1 && koncni != start) {
        vector<int> indices;
        visited[koncni] = true;

        for (auto i : rg[koncni]) {
            g[i].erase(koncni);
            indices.push_back(i);
        }
        koncni = -1;
        for (auto i: indices) {
            if (g[i].size() == 0) {
                if (koncni != -1) {
                    cout << "NE" << endl;
                    return 0;
                }
                koncni = i;
            }
        }
    }
    
    
    if (koncni == start) {
        bool ok = true;
        for (auto i : visited) ok &= i;
        if (ok) cout << "DA" << endl;
        else cout << "NE" << endl;
        return 0;
    }
        
    queue<int> q;
    q.push(start);
    
    while (q.size()) {
        int a = q.front();
        q.pop();
        
        for (int i : g[a]) {
            if (!visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
    
    bool ok = true;
    for (auto i : visited) ok &= i;
    if (ok) cout << "DA" << endl;
    else cout << "NE" << endl;    
    
    return 0;
}