Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 5,363 MiB 0,010 s OK
#2 3/3 5,453 MiB 0,010 s OK
#3 3/3 5,457 MiB 0,010 s OK
#4 3/3 5,453 MiB 0,010 s OK
#5 0/3 5,367 MiB 0,010 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#6 3/3 5,367 MiB 0,010 s OK
#7 3/3 5,453 MiB 0,004 s OK
#8 3/3 5,367 MiB 0,010 s OK
#9 3/3 5,363 MiB 0,010 s OK
#10 3/3 5,367 MiB 0,010 s OK
#11 0/3 5,453 MiB 0,010 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#12 0/3 5,371 MiB 0,010 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#13 3/3 5,371 MiB 0,004 s OK
#14 3/3 5,367 MiB 0,004 s OK
#15 0/3 5,457 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#16 0/3 5,387 MiB 0,010 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#17 0/3 5,387 MiB 0,010 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#18 0/3 5,383 MiB 0,010 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#19 3/3 5,469 MiB 0,010 s OK
#20 3/3 5,566 MiB 0,022 s OK
#21 0/4 8,148 MiB 0,203 s Napaka med izvajanjem / ob izhodu
#22 0/4 13,617 MiB 0,251 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#23 0/4 13,133 MiB 0,245 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#24 0/4 9,141 MiB 0,221 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#25 0/4 7,934 MiB 0,227 s Napačen odgovor
Tvoj izhod:
​NE
<<<EOF>>>
Pravilen izhod:
​DA
<<<EOF>>>
#26 0/4 6,801 MiB 0,109 s Napaka med izvajanjem / ob izhodu
#27 4/4 10,809 MiB 0,227 s OK
#28 4/4 9,336 MiB 0,227 s OK
#29 4/4 7,938 MiB 0,234 s OK
#30 4/4 7,098 MiB 0,204 s OK

Ocenjevani program (trgovec.cpp):
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <map>
#include <functional>
#include <numeric>
#include <stack>
#include <sstream>
#include <unistd.h>
#include <stdio.h>

using namespace std;

int n, m, s;

struct Node {
    vector<int> adj;
};

Node graf[100000];
stack<int> Stack;
bool onStack[100000];
int Indices;
int Index[100000];
int LowLink[100000];
int component[100000];
int numComponents;

void tarjanDFS(int i) {
    Indices++;
    Index[i] = Indices;
    LowLink[i] = Indices;
    Stack.push(i);
    onStack[i]=true;
    for(int j=0; j<graf[i].adj.size(); j++) {
        int w = graf[i].adj[j];
        if(Index[w]==0) {
            tarjanDFS(w);
            LowLink[i] = min(LowLink[i], LowLink[w]);
        } else if(onStack[w]) {
            LowLink[i] = min(LowLink[i], Index[w]);
        }
        if(LowLink[i] == Index[i]) {
            int w=0;
            do {
                if(Stack.empty()) {
                    break;
                }

                w = Stack.top();
                Stack.pop();
                component[w] = numComponents;
                onStack[w] = false;
            } while(i!=w && !Stack.empty());
            numComponents++;
        }
    }
}


int main(int argc, char** argv)
{
   cin >> n >> m >> s;

   for(int i=0; i<m; i++) {
        int startPos, endPos;
        cin >> startPos >> endPos;
        graf[startPos].adj.push_back(endPos);
   }


    Indices = 0;
    for(int i=n; i>0; i--) {
        onStack[i] = LowLink[i] = Index[i] = 0;
    }

    numComponents = 0;

    tarjanDFS(s);

    cout << (component[numComponents] == 1 ? "DA" : "NE") << endl;

}