Rezultati

Up. imeNalogaJezikRezultatČas oddaje
finalsolution-2017 Prijateljske besede C++ 100/100OK 20. apr '17 @ 18:02

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 2,707 MiB 0,004 s OK
#2 12/12 2,887 MiB 0,004 s OK
#3 12/12 3,848 MiB 0,040 s OK
#4 12/12 3,992 MiB 0,040 s OK
#5 13/13 4,004 MiB 0,022 s OK
#6 13/13 3,898 MiB 0,034 s OK
#7 13/13 4,215 MiB 0,028 s OK
#8 13/13 3,895 MiB 0,034 s OK

Ocenjevani program (prijateljskebesede.cpp):
#include <stdio.h>
#include <string.h>
#include <string>
#include <set>
#include <map>
#include <queue>

typedef std::set<std::string> str_set_t;

char B[12];
std::queue<std::string> s_queue;
std::set<std::string> s_matches;
std::map<std::string, str_set_t> s_start;
std::map<std::string, str_set_t> s_end;
std::map<std::string, int> s_count;

static std::string get_start(std::string &s) {
    return s.substr(0, 3);
}

static std::string get_end(std::string &s) {
    return s.substr(s.size() - 3, 3);
}

int main() {
    int i = 0, n = 0, t = 0;
    scanf("%d %s", &n, B);
    std::string bs = std::string(B);
    s_queue.push(bs);
    s_matches.insert(bs);
    s_count[bs]++;
    for (i = 1; i < n; i++) {
        scanf("%s", B);
        std::string s = std::string(B);
        s_start[get_start(s)].insert(s);
        s_end[get_end(s)].insert(s);
        s_count[s]++;
    }
    while (!s_queue.empty()) {
        std::string k = s_queue.front();
        s_queue.pop();
        std::string ks = get_start(k);
        std::string ke = get_end(k);
        if (s_start.count(ks) != 0) {
            str_set_t ss = s_start[ks];
            s_start.erase(ks);
            for (auto it : ss) {
                if (s_matches.count(it) != 0) continue;
                s_queue.push(it);
                s_matches.insert(it);
            }
        }
        if (s_end.count(ke) != 0) {
            str_set_t ss = s_end[ke];
            s_end.erase(ke);
            for (auto it : ss) {
                if (s_matches.count(it) != 0) continue;
                s_queue.push(it);
                s_matches.insert(it);
            }
        }
    }
    for (auto it : s_matches) t += s_count[it];
    printf("%d\n", t);
    return 0;
}