Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 3,133 MiB 0,004 s OK
#2 12/12 3,219 MiB 0,004 s OK
#3 12/12 3,527 MiB 0,132 s OK
#4 12/12 3,297 MiB 0,120 s OK
#5 13/13 3,328 MiB 0,114 s OK
#6 13/13 3,270 MiB 0,114 s OK
#7 13/13 3,258 MiB 0,107 s OK
#8 13/13 3,270 MiB 0,126 s OK

Ocenjevani program (pri.cpp):
#include <iostream>
#include <algorithm>
#include <array>
#include <complex>
#include <cmath>
#include <functional>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <utility>

using namespace std;

typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<double> vd;

bool ok(const string& s, const string& t) {
    if (s[0] == t[0] && s[1] == t[1] && s[2] == t[2]) return true;
    int ls = s.size(); int lt = t.size();
    if (s[ls-1] == t[lt-1] && s[ls-2] == t[lt-2] && s[ls-3] == t[lt-3]) return true;
    return false;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<string> besede(n);
    for (int i = 0; i < n; ++i) {
        cin >> besede[i];
    }
    
    vvi graf(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (ok(besede[i], besede[j])) {
                graf[i].push_back(j);
                graf[j].push_back(i);
            }
        }
    }
    
    queue<int> q;
    q.push(0);
    int size = 0;
    vector<bool> v(n, false);
    while (!q.empty()) {
        int c = q.front();
        q.pop();
        
        if (v[c]) continue;
        v[c] = true;
        
        size++;
        
        for (int x : graf[c]) {
            if (!v[x]) {
                q.push(x);
            }
        }
    }
    
    cout << size << endl;
    
    return 0;
}