Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 3,336 MiB 0,004 s OK
#2 12/12 3,285 MiB 0,010 s OK
#3 12/12 3,336 MiB 2,172 s OK
#4 12/12 3,344 MiB 1,703 s OK
#5 13/13 3,289 MiB 1,727 s OK
#6 13/13 3,289 MiB 1,959 s OK
#7 13/13 3,348 MiB 1,520 s OK
#8 13/13 3,289 MiB 1,758 s OK

Ocenjevani program (PrijateljskeBesede.cpp):
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 3111

string s[maxn];
int root[maxn];

int rooting(int x){
    if(root[x] == x) 
        return x;
    return (root[x] = rooting(root[x]));
}

bool check(string a, string b){
    string z1 = a.substr(0, 3);
    string z2 = b.substr(0, 3);
    string k1 = a.substr(a.length() - 3, 3);
    string k2 = b.substr(b.length() - 3, 3);
    if(z1 == z2 || k1 == k2)
        return 1;
    return 0;
}


int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> s[i];
        root[i] = i;        
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            bool b = check(s[i], s[j]);
            int ri = rooting(i);
            int rj = rooting(j);
            if(b && (rj != ri)){
                root[rj] = ri;              
            }
                
        }
    }
    for(int i = 0; i < n; i++)
        rooting(i);
    
    int r1 = root[0];
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(root[i] == r1)
            ans++;
    }
    printf("%d", ans);
    return 0;
}