Rezultati

Up. imeNalogaJezikRezultatČas oddaje
qubit-2017 Prijateljske besede C++ 100/100OK 20. apr '17 @ 16:48

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 3,137 MiB 0,004 s OK
#2 12/12 3,219 MiB 0,004 s OK
#3 12/12 4,340 MiB 0,162 s OK
#4 12/12 4,336 MiB 0,150 s OK
#5 13/13 4,262 MiB 0,101 s OK
#6 13/13 4,336 MiB 0,119 s OK
#7 13/13 4,266 MiB 0,101 s OK
#8 13/13 4,262 MiB 0,126 s OK

Ocenjevani program (n5.cpp):
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <queue>

typedef long long ll;

using namespace std;

bool druzabni(string& b1, string& b2) {
    int b1s = b1.size();
    int b2s = b2.size();
    if ((b1[0] == b2[0] && b1[1] == b2[1] && b1[2] == b2[2]) || (b1[b1s - 1] == b2[b2s - 1] && b1[b1s - 2] == b2[b2s - 2] && b1[b1s - 3] == b2[b2s - 3])) return true;
    return false;
}

int main(void) {
    cin.tie(nullptr);
    cin.sync_with_stdio(false);

    int n;
    cin >> n;
    vector<string> bes(n);
    for (int i = 0; i < n; i++) {
        cin >> bes[i];
    }
    vector<vector<bool>> d(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            d[i][j] = d[j][i] = druzabni(bes[i], bes[j]);
        }
    }
    vector<bool> vis(n, false);
    queue<int> q;
    q.push(0);
    vis[0] = true;
    int count = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            if (d[i][cur] && !vis[i]) {
                q.push(i);
                vis[i] = true;
            }
        }
        count++;
    }
    cout << count << "\n";

    return 0;
}