Cod sursa(job #1563659)

Utilizator akaprosAna Kapros akapros Data 6 ianuarie 2016 14:01:25
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
#define maxN 36002
#define maxC 2100
#define maxA 26
#define maxL 17
#define mod 66013
#define pb push_back
using namespace std;

int n, m[maxN], sol, w[maxA];
bool u[maxN];
char s[maxN][maxL];
vector < int > V[mod];
int eq(int x, int y)
{
    int i;
    if (m[x] != m[y])
        return 0;
    for (i = 0; i < m[x]; ++ i)
       if (s[x][i] != s[y][i])
       return 0;
    return 1;
}
bool in_hash(int x, int p)
{
    int i;
    for (i = 0; i < V[x].size(); ++ i)
        if (eq(V[x][i], p))
        {
            V[x][i] = p;
            return 1;
        }
    return 0;
}
int sol_hash(int x)
{
    int i, sol = 0;
    for (i = 0; i < V[x].size(); ++ i)
        if (!u[V[x][i]])
           ++ sol;
    return sol;
}
void read()
{
    int i, k = 0;
    freopen("restante.in", "r", stdin);
    scanf("%d\n", &n);
    while (n --)
    {
        ++ k;
        gets(s[k]);
        m[k] = strlen(s[k]);
        int crypt = 0;
        sort(s[k], s[k] + m[k]);
        for (i = 0; i < m[k]; ++ i)
            crypt = (crypt * maxA + s[k][i] - 'a') % mod;
        if (!in_hash(crypt, k))
            V[crypt].pb(k);
        else
            u[k] = 1;
    }
}
void solve()
{
    int i;
    for (i = 1; i < mod; ++ i)
        sol += sol_hash(i);
}
void write()
{
    freopen("restante.out", "w", stdout);
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}