http://codeforces.com/contest/154

C题

观察能力+Hash。
注意到若两个点 u,v 能成为doubles,那么 u,v 对除了它们之外的其他所有点的连接关系是一样的。这样就可以用 Hash 判同了。
另外,分开判断 u,v 之间是否有连线的情况:没连线直接判,有连线需要加上自身该点。
最后注意用 long long 统计。

(只贴出与题目有关的代码,宏定义见 GitHub

/* 1028 ms, 15660 KB */
const ull B = ull(1e8) + 7;
const int mx = int(1e6) + 5;

ull ha1[mx], ha2[mx] = {1ULL};
int n, m;

void init()
{
    int i;
    Forr(i, 1, n + 1) ha2[i] = ha2[i - 1] * B;
}

ll Cnt(ull *ha)
{
    sort(ha + 1, ha + n + 1);
    int i;
    ll ans = 0, cnt = 0;
    Forr(i, 2, n + 1)
    {
        if (ha[i] == ha[i - 1]) ans += ++cnt;
        else cnt = 0;
    }
    return ans;
}

int main()
{
    int a, b, i;
    SII(n, m);
    init();
    while (m--)
    {
        SII(a, b);
        ha1[a] += ha2[b], ha1[b] += ha2[a];
    }
    Forr(i, 1, n + 1) ha2[i] += ha1[i];
    PL(Cnt(ha1) + Cnt(ha2));
    return 0;
}

Comments

comments powered by Disqus