Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 3,215 MiB 0,004 s OK
#2 12/12 3,441 MiB 0,004 s OK
#3 12/12 11,824 MiB 0,199 s OK
#4 12/12 11,809 MiB 0,181 s OK
#5 13/13 11,762 MiB 0,168 s OK
#6 13/13 11,758 MiB 0,175 s OK
#7 13/13 11,766 MiB 0,168 s OK
#8 13/13 11,797 MiB 0,162 s OK

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

using namespace std;

const int N = 3008;
bool conn[N][N];
bool visited[N];
string words[N];

int n;

bool companion(const string& s1, const string& s2) {
    return equal(s1.begin(), s1.begin() + 3, s2.begin()) ||
            equal(s1.rbegin(), s1.rbegin() + 3, s2.rbegin());
}

int dfs(int x) {
    if(visited[x]) return 0;
    visited[x] = true;

    //cout << words[x] << endl;

    int res = 1;
    for(int j=0;j<n;j++) {
        if(conn[x][j] && ! visited[j]) {
            //cout << words[x] << "->" << words[j] <<endl;
            res += dfs(j);
        }
    }
    return res;
}

int main() {
    //cout << companion("pregovor", "izvor") <<endl;
    //freopen("in.txt", "r", stdin);
    cin>>n;

    for(int i=0;i<n;i++) {
        cin>>words[i];
    }

    /*for(int i=0;i<n;i++) {
        cout <<i<<": "<<words[i]<<endl;
    }*/

    for(int i=0;i<n;i++) {
        conn[i][i] = true;
        for(int j=i+1;j<n;j++) {
            conn[i][j] = conn[j][i] = companion(words[i], words[j]);
            //cout << words[i]<<" "<<words[j] << " "<<conn[i][j]<<endl;
        }
    }

    cout << dfs(0);

    return 0;
}