Rezultati

Up. imeNalogaJezikRezultatČas oddaje
jam-2018 Nič nas ne sme presenetiti! C++ 100/100OK 19. apr '18 @ 19:09

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 3,039 MiB 0,000 s OK
#2 12/12 3,039 MiB 0,000 s OK
#3 12/12 3,031 MiB 0,000 s OK
#4 12/12 17,363 MiB 0,501 s OK
#5 13/13 3,031 MiB 0,000 s OK
#6 13/13 12,098 MiB 0,195 s OK
#7 13/13 12,004 MiB 0,000 s OK
#8 13/13 11,996 MiB 0,000 s OK

Ocenjevani program (main.cpp):
#include <iostream>
#include <vector>
#include <list>
#include <utility>
#include <set>
#include <algorithm>

using namespace std;

int main() {
  int n, st_primerov;
  cin >> n >> st_primerov;

  vector<set<int>> edges;
  for (int i = 0; i < n + 1; i++) {
    set<int> temp;
    edges.push_back(temp);
  }

  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    edges[a].insert(b);
  }

  for (int i = 0; i < st_primerov; i++) {
    int st_za_not;
    cin >> st_za_not;
    set<int> tab;

    for (int j = 0; j < st_za_not; j++) {
      int st;
      cin >> st;
      tab.insert(st);
    }

    int st_povezav = 0;

    if (tab.size() < 100) {
      for (int from : tab)
        for (int el : tab)
          if (edges[from].find(el) != edges[from].end())
            st_povezav++;
    } else {
      for (int from : tab) {
        if (edges[from].size() > 1000) {
          auto ena = tab.begin();
          auto dve = edges[from].begin();
          auto kon = edges[from].end();

          while (ena != tab.end() && dve != kon) {
            while (*ena < *dve && ena != tab.end())
              ++ena;
            if (ena == kon)
              break;

            if (*ena == *dve) {
              st_povezav++;
              ++ena;
              ++dve;
              if (ena == tab.begin() || dve == kon) break;
            }

            while (*dve < *ena && dve != kon)
              ++dve;
            if (dve == kon)
              break;

            if (*ena == *dve) {
              st_povezav++;
              ++ena;
              ++dve;
              if (ena == tab.begin() || dve == kon) break;
            }
          }

        } else {
          for (int el : edges[from])
            if (tab.find(el) != tab.end())
              st_povezav++;
        }
      }
    }

    if (st_povezav == st_za_not - 1)
      cout << "ALAAAARHM" << endl;
    else
      cout <<"NASLEDNJI" << endl;
  }
}