Rezultati

Up. imeNalogaJezikRezultatČas oddaje
jam-2018 Dolenjec C++ 100/100OK 10. maj '18 @ 18:57

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 3,004 MiB 0,004 s OK
#2 3/3 3,195 MiB 0,004 s OK
#3 3/3 3,004 MiB 0,004 s OK
#4 3/3 3,199 MiB 0,004 s OK
#5 3/3 3,199 MiB 0,004 s OK
#6 3/3 3,008 MiB 0,004 s OK
#7 3/3 3,195 MiB 0,000 s OK
#8 3/3 3,203 MiB 0,004 s OK
#9 3/3 3,203 MiB 0,004 s OK
#10 3/3 3,203 MiB 0,004 s OK
#11 3/3 3,008 MiB 0,000 s OK
#12 3/3 3,008 MiB 0,004 s OK
#13 3/3 3,215 MiB 0,000 s OK
#14 3/3 3,016 MiB 0,004 s OK
#15 3/3 3,211 MiB 0,004 s OK
#16 3/3 3,211 MiB 0,004 s OK
#17 3/3 3,215 MiB 0,004 s OK
#18 3/3 3,059 MiB 0,004 s OK
#19 3/3 3,250 MiB 0,000 s OK
#20 3/3 3,254 MiB 0,000 s OK
#21 3/3 3,262 MiB 0,004 s OK
#22 3/3 4,137 MiB 0,003 s OK
#23 3/3 23,820 MiB 0,375 s OK
#24 3/3 19,250 MiB 0,325 s OK
#25 3/3 18,926 MiB 0,302 s OK
#26 3/3 15,633 MiB 0,292 s OK
#27 3/3 14,500 MiB 0,256 s OK
#28 3/3 20,766 MiB 0,308 s OK
#29 3/3 19,125 MiB 0,271 s OK
#30 3/3 15,422 MiB 0,231 s OK
#31 3/3 14,484 MiB 0,249 s OK
#32 3/3 13,176 MiB 0,226 s OK
#33 4/4 3,004 MiB 0,004 s OK

Ocenjevani program (main.cpp):
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <list>


using namespace std;

class Edge;

class Vertex {
public:
  bool gostilna = false, checked = false, onpath = false;

  list<Edge *> in, out;

};

class Edge {
public:
  Vertex *to, *from;

  Edge(Vertex *from, Vertex *to) : from(from), to(to) {}
};


vector<Vertex *> vertices;

int st_stavb, st_cest, st_gostiln, q0;

Vertex *rek(Vertex *vertex) {
  if (vertex->onpath) {
    if (vertex->gostilna) {
      cout << "DA" << endl;
      exit(0);
    }
    return vertex;
  }
  if (vertex->checked)
    return nullptr;

  vertex->onpath = true;
  vertex->checked = true;

  for (Edge *edge : vertex->out) {
    Vertex *r = rek(edge->to);
    if (r) {
      if (vertex->gostilna) {
        cout << "DA" << endl;
        exit(0);
      }
      if (vertex == r)
        continue;

      for (Edge *o : vertex->out) {
        r->out.push_back(o);
        o->from = r;
      }

      for (Edge *o : vertex->in) {
        r->in.push_back(o);
        o->to = r;
      }

      vertex->onpath = false;
      return r;
    }
  }

  vertex->onpath = false;
  return nullptr;
}

int main() {
  cin >> st_stavb >> st_cest >> st_gostiln >> q0;

  for (int i = 0; i < st_stavb + 1; i++)
    vertices.push_back(new Vertex());

  for (int i = 0; i < st_gostiln; i++) {
    int g;
    cin >> g;
    vertices[g]->gostilna = true;
  }

  for (int i = 0; i < st_cest; i++) {
    int from, to;
    cin >> from >> to;
    Edge *edge = new Edge(vertices[from], vertices[to]);
    vertices[from]->out.push_back(edge);
    vertices[to]->in.push_back(edge);
  }

  rek(vertices[q0]);

  cout << "NE" << endl;
}